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.
-
Review all the written homework assignments:
-
Assignment 1
-
Assignment 2
-
Some practice questions on recurrences.
-
Assignment 3
-
Assignment 4
-
Assignment 5
-
Assignment 6
-
Assignment 7
-
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.
-
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.
-
Know how to describe common algorithms such as mergesort, quicksort, or
binary search, to name just a few.
-
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.)
-
Look at
the final examination from Fall 1998
Postscript format.
Plain text.
-
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.