Final Exam: Outline
The final exam will be given Wednesday, May 4, from 7:00 to 9:00 in
Warren Weaver, room 101. It is
closed book and closed notes. You will not need a calculator.
You should know the following algorithms well enough to carry them out:
depth-first search; breadth-first search; iterative deepening; hill-climbing;
game tree evaluation with alpha-beta pruning; Davis-Putnam algorithm;
conversion to clausal form and resolution theorem proving for both
propositional calculus and predicate calculus; forward-chaining over
Horn clauses; backward chaining over Horn clauses; SAT-based planning;
- Blind search -- R+N chap 3 through 3.5.
- Informed search --- R+N secs 4.3.
- Game playing -- R+N chapter 6 through 6.4.
- Automated reasoning -- R+N chaps 7 through 7.6; chapter 8 through
8.3; chapter 9; handouts.
- Propositional Calculus
- Davis-Putnam algorithm
- Predicate Calculus
- Resolution theorem proving
- Horn theories; backward and forward chaining.
- Planning (chapter 11 except 11.4)
- Progression planning
- Regression planning
- SAT-based planning
- STRIPS representation
- Partial order planner
- Markov decision processes (chap. 17 through 17.3)
You should understand the following algorithms well, though I would not
ask you to carry them out on an exam: GSAT; simulating annealing;
value and policy iteration for Markov decision processes.
The following topics were discussed in class but will NOT be on
the final exam: Prolog, situation calculus, PDDL. I hope to have
time to discuss the GraphPlan planner on April 20, but will not
include it on the final exam.
I will hand out some sample problems on April 20 and will go over them
on April 27. I am happy to devote as much of class time on April 27 as
you want to review.