CPSC 311: Review for Exam 1
Spring 2004
You may bring one 8.5-by-11 inch sheet of paper with your own
notes on it to the exam. You may write on both sides.
Review the following:
- Lectures through Feb 25 (ends with hashing).
- Readings from textbook:
pp 3-4;
Chs 1-4 (skip Sec 4.4);
pp 123-126;
Chs 6-9 (skip analysis of randomized select in Ch 9);
pp 197-199;
Ch 10 (review from CPSC 211);
Ch 12 (skip Sec 12.4);
Ch 18;
Ch 11 (skip Subsec 11.3.3 and Sec 11.5).
- Quizzes 1-6 and their solutions (given in class).
- Homeworks 1-3 and their solutions (available from course web page).
The format of the exam will be some short answers and some
"work-out" problems.
Here are some suggestions for things to know:
- asymptotic analysis and big-oh notation
- solving recurrences with and without master theorem
- binary heaps
- sorting algorithms heapsort, quicksort, counting sort, radix sort,
bucket sort.
- Know how the algorithms work (don't memorize the
pseudocode) so that you could simulate their behavior on a
particular input.
- Know the asymptotic analyses for worst-case running time.
- Know the best-case and average-case running times.
- Know if they are stable and/or in-place.
- the randomized and the deterministic selection algorithms
- Know how the algorithms work.
- Know the asymptotic analyses for worst-case running time.
- Know the best-case and average-case running times.
- binary search trees
- Know the algorithms for insert, search, delete, min, max,
pred, succ, and sorting.
- Know the asymptotic analyses for the worst-case running times for
the operations.
- Know the average running times.
- B-trees
- Know the asymptotic analyses for the worst-case running times for
the operations insert, search, delete, min, max, pred, succ,
and sorting.
- Know the algorithm for search and the general idea of the
algorithms for insert and delete.
- Hash tables.
- Know some characteristics of good hash functions.
- Know the algorithms for insert, search and delete for both
chaining and open addressing.
- Think about how to do min, max, pred, succ, and sorting.
- Know the asymptotic analyses for the worst-case and average
case running times for the operations.