Spring 2004

The final exam will be similar in style to Exams 1 and 2. It will be cumulative. There will be additional emphasis (in short answer questions) on the material since Exam 2.

In addition to the material for Exams 1 and 2, review the following:

- lecture notes, Slides 284-348
- Quizzes 11 and 12 and their solutions (given in class)
- lab activities

- Object-oriented software engineering: software lifecycle, etc.
(details of CRC diagrams are not important)
- File systems: indexed files, hashed files, etc.
- Databases: serializability, 2-phase locking, committing and aborting
transactions.
- Artificial intelligence: goals, production systems, ways to search
the state space (breadth-first vs. depth-first).
- Complexity theory: definitions of time complexity of an
*algorithm*and time complexity of a*problem*, and the class P; idea of NP-complete problem; definition of traveling salesman problem; fact that no one knows whether NP-complete problems can be solved in polynomial time or not. - Computability theory: fact that there are functions / problems that
cannot be computed / solved by an algorithm. (You do not need to
know the
*proof*of this result.)