The final exam is cumulative but more weight (probably roughly half) will be given to topics covered since the second midterm. So, review all topics covered in lecture or homework assignments except a few topics clearly marked as optional (notably AVL deletion and the details of the proof for the lower bound for comparison sorting). Also not included are all the topic from lectures 18 and 23(NP-Completeness, Network Flow, programming languages, etc.). The main topics that came after the topics covered by the midterms are preserving software abstractions, everything about sorting, locality, and our introduction to parallelism.
Our exam will consist of various types of short-answer questions. You may be asked to write or read Java code or pseudocode. It will be similar in style to the midterms, but covering different topics and with the potential for slightly different styles of questions.
Below we have repeated the sample midterms from the study guides for the two midterms. Because our final exam is cumulative, it makes sense to provide questions from old midterm exams. In addition, some of these exams have questons about topics like locality. For the topics since the midterms, we have provided a few additional sample questions, but we do not have as many available.
Please understand these caveats:
Sample exams:
Midterm 1:
Midterm 2:
Final exam:
Some additional questions
unsolved
solved
Note: