COS 402: Introduction to Artificial Intelligence

The final will be held at 9:00am on Tuesday, January 24 in Friend Center 006.  This will be a three-hour exam for which you will be given 3.5 hours (unless someone objects to having the extra time).

If you do better on the exam than the homeworks, then the final exam will be worth 35% of your final grade .  Otherwise, if you did better on the homeworks than the exam, it will be worth only 25% of your grade.

What to bring

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.

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.

Sample exam

Here is a sample exam.  The actual exam will be largely of the same format, but will be substantially longer (probably 1.5 to 2 times as long).  Solutions are not being provided, but you are welcome to ask me or the TA's or other students for help.  The TA's also plan to hold a special question and answer session sometime during the week before the exam (watch your email for the exact date and time).

What will be covered

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.

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.

• 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
  • 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
• learning parameters of a Bayes net
• principles:
  • maximum likelihood
  • MAP
  • full Bayesian
• EM
• learning in MDP's (reinforcement learning)
  • model-based approach (adaptive dynamic programming)
  • exploration versus exploitation
  • model-free approach
    • TD algorithms
    • Q-learning
• philosophy / future of AI
  • Turing test
  • Chinese room experiment

Good luck!