Lecture: 3 hours
Discussion: 1 hour

Catalog Description:
Design and implementation of intelligent computer systems. Intelligent search, adversarial search in games, reasoning with graphical models, reinforcement learning and connectionist machines

Prerequisite: ECS 060 or ECS 032B or ECS 036C

Credit restrictions, cross listings: None

Summary of course contents

  1. Informed Search
    1. Time and space complexity of uninformed search
    2. The A* Informed search algorithm and inventing admissible heuristics
    3. Proofs of optimality and optimal efficiency
  2. Adversarial Search
    1. Zero-sum games
    2. Game trees and evaluation functions
    3. The mini-max algorithm
    4. The alpha-beta algorithm
    5. Extensions to multi-player and games of chance
    6. Proofs of best case, worst case and expected case time complexity
  3. Graphical Models of Learning
    1. Page rank models and random walks on graph
    2. Basic propositional graphs
    3. Three types of queries
    4. The intractability of general inference of graphs
    5. Approximation algorithms using MCMC samplers
  4. Connectionist Architectures
    1. Perceptrons, Linear Units and Sigmoid functions
    2. Learning single units
    3. Learning networks of units
  5. Reinforcement Learning
    1. Markov decision processes
    2. Cumulative discount rewards
    3. Learning Q-tables
    4. Proofs of convergence and anytime behavior

Three programming assignments emphasize basic concepts, with open-ended design components included. Grading based on design as well as grasp of concepts. Design involves decisions as to method used and specific application to real application areas.

Students must exercise considerable design skills in the project and also in homework assignments. Open-ended choices include choice of methodologies to be used in design and implementation, and evaluation of effectiveness of method used. Examinations also include design-oriented questions.

Goals:  Students will learn specific techniques including informed search, adversarial search for games, reasoning with graphical models, connectionist architectures and reinforcement learning

Illustrative reading
S. Russell and P. Norvig, Artificial Intelligence: A Modern Approach, 3rd edition,  Prentice Hall, 2009.

Computer Usage:
Type: Sparcstation running UNIX
Languages: Primarily Prolog, LISP, or C
Proficiency Level Attained: Through four homework assignments and a project where the students design a large artificial intelligence program.

ABET Category Content:
Engineering Science: 2 units
Engineering Design: 1 unit

GE3: Science & Engineering

Overlap: None

Instructor: I. Davidson

History: Updated 9.7.2018 (CSUGA): Prerequisites updated to include new lower division ECS series courses. 2012.10.20 (I. Davidson): changed the title (Introduction to), revamped the catalog description, and provided a revised summary of course contents for ICMS (none had been uploaded before). Reduced 140A prereq to 60. The new course description reflects the class as currently taught.  Prior updates to course description provided by Davidson (date unknown) were not uploaded to ICMS or the Department’s web page. Original expanded course description by K. Levitt dated to January 1993


1 X an ability to apply knowledge of mathematics, science, computing, and engineering
2 X an ability to design and conduct experiments, as well as to analyze and interpret data
3 an ability to design, implement, and evaluate a system, process, component, or program to meet desired needs, within realistic constraints such as economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability
4 X an ability to function on multi-disciplinary teams
5 X an ability to identify, formulate, and solve computer science and engineering problems  and define the computing requirements appropriate to their solutions
6 an understanding of professional, ethical, legal, security and social issues and responsibilities
7 an ability to communicate effectively with a range of audiences
8 X the broad education necessary to understand the impact of computer science and engineering solutions in a global and societal context
9 a recognition of the need for, and an ability to engage in life-long learning
10 X knowledge of contemporary issues
11 X an ability to use current techniques, skills, and tools necessary for computing and engineering practice
12 X an ability to apply mathematical foundations, algorithmic principles, and computer science and engineering theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices
13 X an ability to apply design and development principles in the construction of software systems or computer systems of varying complexity