Final Exam: Outline
The final exam will be given Wednesday, May 3, 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; backward-chaining and
Horn clauses; Naive Bayes learning, 1R learning, ID3 learning (though
I will not give you any problem that involves computing entropies).
- 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.
- Probabilistic reasoning. R&N chap. 13.
- Machine learning:
- Overview. R&N chap 18 through 18.2.
- 1R algorithm. Handout.
- Nearest neighbors. R&N sec. 20.4 except "Kernel methods." pp. 733-5.
- Naive Bayes. Xerox from Mitchell.
- Decision trees and ID3. R&N sec. 18.3, pp. 653-660. Handout.
- Neural networks: Perceptron and back-propagation. R&N sec. 20.5,
- Evaluation of classification algorithms: Training and test set.
R&N pp. 660-661.
You should understand the following algorithms well, though I would not
ask you to carry them out on an exam: GSAT; simulating annealing;
perceptron learning and back-propagation.