Final Exam: Outline
The final exam will be given
Monday May 10 from 7:00 to 9:00 in room 202. It is
closed book and closed notes.
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 for propositional calculus and predicate calculus;
resolution theorem proving for
predicate calculus; nearest neighbors learning;
Naive Bayes learning; 1R learning; ID3 learning (though
I will not give you any problem that involves computing entropies); k-means
- Blind search -- R+N chap 3 through 3.4.
- Hill climbing --- R+N chap 4 through 4.1.3
- Game playing -- R+N chapter 5 through 5.3.
- Automated reasoning --
- Propositional Calculus -- R+N chap 7 + handouts
- Davis-Putnam algorithm
- Predicate Calculus -- R+N chap 8 + handouts
- Resolution theorem proving -- R+N chap 9 through 9.2 + handouts
- Probabilistic reasoning. R+N chap. 13, chap 14 through 14.2.
- Machine learning:
- Overview. R&N chap 18 through 18.2.
- 1R algorithm. Handout.
- Nearest neighbors. R&N sec. 18.8 through 18.8.2.
- Naive Bayes. R+N section 20.2.2 (pp. 808-809). Handout.
- Decision trees and ID3. R&N sec. 18.3, pp. 653-660. Handouts.
- Evaluation of classification algorithms.
R&N section 18.4, 22.3.2 (p. 869).
- Clustering. Handout
You should understand the following algorithms well, though I would not
ask you to carry them out on an exam: hill-climbing with sideways motion
and/or random restart; simulating annealing.