CS 188 Final Preparation

CS 188: Artificial Intelligence, Spring 2007

About the Exam

The final will be held on Tuesday, May 15th, at 50 Birge, starting promptly at 8:10am and ending at 11am.

The final will be closed notes, books, laptops, and people. However, you may use two pages (double sided) of cheat sheets 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:

Last term's syllabus was somewhat different in order, and so the exam topics do not align perfectly. Specific questions indicated (post midterm material) are similar in complexity to the final. For pre-midterm material, the Spring 2007 midterm is a good estimate of the level of complexity for the final.

Practice final (from Spring 2006) (the classification problem (Q 4), the bayes net problem (Q 6), and the MDP/RL problem (Q 7) are similar in complexity to what you can expect for the final)

Spring 06 midterm, (solutions) (the Naive Bayes question (Question 4) is similar in complexity to what you can expect in the final)

Fall 06 midterm with solutions (the HMM problem (Q 3) is similar in complexity to what you can expect in the final

Spring 06 practice final, (solutions) (the MDP question (Question 8) is similar in complexity to what you might expect in the final)

Spring 07 midterm with solutions

Spring 06 practice midterm, (solutions)

You can also look at old exams from previous semesters.

Review Sessions

Review: Thursday 5/8, in class 9:40 - 11 AM (post midterm topics)

General Final Review: Thursday, 5/10/2007, 4 PM at 306 SODA

Possible Final Topics

All topics from the midterm and after are included in the list of topics for the final.

Search:

BFS, DFS, UCS, A*, Greedy search
Search algorithms' strengths and weaknesses
Properties: completeness, optimality
Admissibility and heursitics
Local search
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

Logic:

Basics: Entailment, Validity, Satisfiability
Propositional Logic
Propositional Resolution (conversion to CNF)
First Order Logic (relations, objects, functions)
Quantifiers

Probability and Graphical Models:

Basics: Joint Distribution, Conditional Distribution, Chain Rule, Bayes Rule
Graphical Models, Structure, CPT representation
Conditional independence / Bayes' ball
Be able to draw an appropriate BN for a domain
Inference (enumeration), prior sampling, rejection sampling, likelihood weighting

Hidden Markov Models:

Markov and hidden Markov chains
Forward algorithm
Viterbi algorithm

Classification:

Basic concepts: generalization, overfitting, supervised, unsupervised
Naive Bayes
Perceptrons

Decisions:

The MEU principle
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

Advanced Topics:

Clustering and the K-means algorithm
Applications to NLP