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.)