## Final Exam Information |
## Fall 2012 |

The final will be held at 1:30pm on Tuesday, January 22 in room 50 of McCosh Hall.

This will be a three-hour exam. Although I hope it will not happen, there is always the chance that an exam such as this one will extend slightly longer than anticipated. If this would be a problem for you (for instance, because you have another appointment right after the exam), please let me know as soon as possible.

The exam will be ** closed book**. You may * not* use the text book, your notes, a computer or any other materials
during the exam. However, **you may bring a one-page
"cheat sheet"** consisting of a single, ordinary 8.5"x11"
blank sheet of paper with whatever notes you wish written upon it. You may
write on both the front and the back. However, it must be * handwritten* (not
computer generated or photocopied) in * your own * handwriting. We
may (or may not) collect these at the conclusion of the exam.

Also, **be sure to bring a calculator.** However, you may only use
the basic math functions on the calculator (i.e., plus, times, log, sin, exp,
etc.); you may *not* use any programming functionality, text storage or
other advanced capabilities that might be built into your calculator. You
may not use your cell phone or similar device as a calculator.

** You will be at a significant disadvantage** if you
forget either the cheat sheet or the calculator . It is your own
responsibility to remember to bring both.

Cell phones, laptops and all other devices that can be used for any form of communication must be completely turned off throughout the entire exam.

*All *students taking the exam must agree to be bound by Princeton's
undergraduate honor code. This includes both undergraduate *and graduate*
students, regardless of whether or not they are actually enrolled in the course.
If you are unfamiliar with this honor system, please take a minute to read its
terms here.

Here is a sample exam. The actual exam will be
largely of the same format, but will be *substantially longer* and more
comprehensive in terms of the topics covered. Solutions
for the short-answer sections are available here.
(Please let me know if you detect any errors.) Solutions for the longer
problems at the end of the exam are not being provided, but you are welcome to
ask me or the other staff members or other students for help. See information below on
the question-and-answer session.

We will hold a question-and-answer session on Friday, January 18 at 11am-12:30pm in the small auditorium (room 105) of the computer science building. Note that the purpose of this session is only to answer your questions (not, for instance, to conduct a systematic review of the entire course).

Course staff members will continue to hold regular office hours through the day of the final. In addition, Rajesh will hold additional office hours on Monday, January 21 at 4-5pm (usual place).

In principle, anything covered in lecture or in the assigned readings is "fair game", including material covered at the very end of the course (such as EM and Q-learning). Realistically, you can expect that the emphasis will be placed on those same topics that were emphasized in lecture and on the homeworks.

Below is a list of topics, concepts and algorithms that you should be familiar with. I have attempted to make this an exhaustive list, although I cannot guarantee that I did not miss an item or two.

- successes and limitations of AI
- Turing test
- search and problem solving
- properties of search algorithms (completeness, optimality, time and space efficiency)

- uninformed (blind) search
- BFS
- uniform-cost search
- DFS
- depth-limited search
- IDS
- bidirectional search

- informed (heuristic) search
- best-first search
- A*
- heuristic functions (consistent, admissible)

- local search
- objective function
- hill climbing
- simulated annealing
- beam search
- genetic algorithms

- adversarial search
- minimax algorithm
- alpha-beta pruning
- evaluation functions
- tricks for speeding up game playing programs

- logic
- elements of a logic (semantics, syntax, models, etc.)
- entailment
- propositional logic (symbols, literals, etc.)
- horn clauses/sentences

- inference algorithms
- soundness and completeness
- model checking
- inference rules
- resolution
- DPLL
- walksat

- formulating problems as satisfiability instances
- planning problems

- first-order logic
- probability
- events and atomic events
- random variables
- distribution
- joint distribution
- conditional probability
- marginal probability
- independence
- conditional independence
- Bayes' rule
- expected value
- conditional expected value

- Naive Bayes algorithm
- Bayesian networks
- meaning and interpretation
- Markov blanket
- inference
- variable elimination
- direct sampling, rejection sampling, likelihood weighting
- MCMC

- Markov chains
- stationary distribution

- temporal models
- states, observations, evidence, etc.
- HMM's
- belief state
- filtering
- prediction
- smoothing (forward-backwards algorithm)
- Viterbi
- Kalman filters
- DBN's
- particle filters

- speech recognition
- phones, phonemes, frames, etc.
- triphone model
- three-state phone model
- acoustic model
- language model
- bigram/trigram model
- pronunciation model

- utility
- MDP's
- states, rewards, actions, etc.
- policy
- optimal policy
- utility
- discounted reward
- Bellman equations
- value iteration
- policy evaluation
- policy iteration
- convergence properties
- policy improvement theorem

- POMDP's
- learning
- types of learning problems (supervised, regression, classification, etc.)
- Occam's razor
- conditions for effective learning
- features (a.k.a. attributes or dimensions)
- class (a.k.a. label or output)
- instances and examples
- training error, test error, generalization error
- hypotheses
- overfitting
- theory - PAC bounds

- learning algorithms
- decision trees
- how to grow - impurity measures
- pruning

- AdaBoost
- weak hypotheses and weak learning

- SVM's
- kernel trick

- neural nets
- gradient descent and backprop

- decision trees
- learning parameters of a Bayes net
- principles:
- maximum likelihood
- MAP

- EM
- learning in MDP's (reinforcement learning)
- model-based approach (adaptive dynamic programming)
- exploration versus exploitation
- model-free approach
- TD algorithms
- Q-learning