CS 188 Final Preparation

CS 188: Artificial Intelligence, Fall 2007

Announcements

Course Info

Lectures

Projects

FAQ

Section

Demos

Newsgroup

About the Exam

The final will be held on Wednesday, December 19th, starting promptly at 12:30pm and ending at 3:30pm.

The final will be closed notes, books, laptops, and people. However, you may use two pages of notes of your own design (group design ok but not recommended). You may also use a basic calculator, which will not be required, but which may be helpful.

Practice Exams

Practice exams:

Fall 06 Final

Fall 06 Midterm 1, (solutions)

Spring 06 midterm, (solutions)

Spring 06 practice midterm, (solutions)

Spring 06 final

Spring 06 practice final, (solutions)

Note that topics covered vary from term to term and so exam topics and focus may vary.

You can also look at old exams from previous semesters.

Review Sessions and Office Hours

The Primary Review Session: Sunday, 12/16 from 6pm-9pm in 306 Soda.

We will hold several office hours between now and the final. Each hour, we will focus on a particular theme for each one. We can, of course, answer general questions during themed office hours, but will focus on the topics listed.

CSPs: Adam, Thursday 12/13, 10-11am in Soda 511
HMMs: Adam, Thursday 12/13, 11-12am in Soda 511
Bayes' Nets: Aria, Thursday 12/13, 1-2pm in Soda 611
General review: Aria, Thursday 12/13, 2-3pm in Soda 611
Search: Ryan, Friday 12/14, 9-10am in Soda 711
Games: Ryan, Friday 12/14, 10-11am in Soda 711
MDPs: Ryan, Friday 12/14, 11-12am in Soda 711
Reinforcement Learning: Ryan, Friday 12/14, 12-1pm in Soda 711
Classification: Simon, Friday 12/14 1-2pm in Soda 711
General review: Simon, Friday 12/14 2-3pm in Soda 711

Possible Final Topics

The final covers the entire semester, not just the second half!

Search:

BFS, DFS, UCS, A*, Greedy search
Search algorithms' strengths and weaknesses
Properties: completeness, optimality
Admissibility and heursitics
Local search
Basic robot motion planning (configuration spaces, etc)
Be able to phrase search problems and create heuristics

Constraint Satisfaction Problems:

Basic definitions and solution with DFS
Forward checking, arc consistency
Be able to phrase CSPs

Games:

Minimax search
Alpha-beta pruning
Expectimax search
Evaluation function design

Decisions:

The MEU principle
Reflex agents and policies
Markov decision processes
Reward functions
Bellman Equations
Value and policy iteration
Be able to phrase a problem as an MDP

Reinforcement Learning:

Exploration vs exploitation
TD value learning / Q-learning
Linear value function approximation

Bayes Nets:

Conditional independence / Bayes' ball
Basics of parameter estimation (maximum likelihood, smoothing)
Inference by enumeration
Inference by sampling
Be able to draw an appropriate BN for a domain
Decision diagrams
Value of information

Hidden Markov Models:

Markov and hidden Markov chains
Forward algorithm
Viterbi algorithm
Particle filtering

Classification:

Basic concepts: hypothesis classes, generalization, overfitting, experimental methodology
The naive Bayes classifier
The perceptron classifier
The nearest neighbor classifier
Estimation and smoothing
Purposes of held-out (validation) data