Mid-term exam

The mid-term exam will be given on Thursday, March 13. It will take the entire class period. It will be open book and open notes, but no computers or electronic devices may be used.

The exam will include all material covered in class through the logic section, except Prof. Fergus' lecture on vision, and only material covered in class. Specifically, it will include the following material:

Natural language processing: Context free grammar and probabilistic CFG. CYK algorithm. Compositional semantics. Ambiguity resolution.
(Russell & Norvig chapter 23 sections 23.1 (all), 23.2 (the beginning section, not 23.2.1 or 23.2.2), plus handouts.)

State space search. State spaces. Depth-first search, breadth-first search, iterative deepening, simple hill-climbing, sideways motion, random restart.
(R&N Chap 3 through 3.4.1, 3.4.3-3.4.5; Chapter 4 through 4.1.1.)

Games playing: AND/OR tree, MIN/MAX tree, alpha-beta pruning.
(R&N chapter 5 through 5.3 except 5.2.2)

Logic: Propositional logic. CNF. Translating sentences into CNF. Davis-Putnam algorithm. Compiling problems into satisfiability.
(R&N chapter 7 through 7.4; 7.6 through 7.6.1. Skim 7.7. Handouts)

You should know the following algorithms well enough to be able to execute them in an exam problem:
CYK parser, depth-first search, breadth-first search, iterative deepening, simple hill-climbing, conversion to CNF, Davis-Putnam algorithm. (I can't ask you to execute hill-climbing with sideways motion or random restart, since it's unlikely that you have a random number generator in your head that you can access.)