This summary of the material to study for the final examination is not yet complete.
The final examination will be comprehensive, but with a greater emphasis on the material since the last examination.

1. Review all the written homework assignments:
   1. Assignment 1
   2. Assignment 2
   3. Some practice questions on recurrences.
   4. Assignment 3
   5. Assignment 4
   6. Assignment 5
   7. Assignment 6
   8. Assignment 7
2. I would certainly expect you to be able to give passable definitions of elementary concepts such as "abstract data type," "sparse matrix," or "lazy deletion," to name just a few.
3. Know basic things about graphs directed graphs, trees (any of the many kinds of trees we discussed), stacks, queues, or priority queues, to name just a few.
4. Know how to describe common algorithms such as mergesort, quicksort, or binary search, to name just a few.
5. Be prepared to answer true/false questions about whether a given problem is NP-complete. For example, is the clique problem NP-complete? Is the 0-1 minimum spanning tree problem NP-complete? Is primality NP-complete? (We have answered all of those in class.)
6. Look at the final examination from Fall 1998 Postscript format. Plain text.
7. Let A be an array of numbers. This code replaces A by its so-called prefix sums in O(n) time.
   For example, if n = 5 and the values of A are initially 3,4,-2,0,1 then, after the code is executed, the values of A will be 3,7,5,5,6.
   Show how the same thing can be accomplished in O(log n) time using n processors working in parallel. Any processor may access (read or write) any memory location, but no two processors may access the same memory location at the same time.
   You can do it without any additional memory, that is, all intermediate values are stored in A itself.
   This algorithm has important practical applications.