##
CPSC 411: Review for Exam 1

Fall 2008

*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 lectures and the reading through Oct 2. Here is a detailed list
of what was covered and will be fair game for the exam:

- introduction and review:
- slides set 1
- boardwork on asymptotic notation
- Chs 1-3

- sorting lower bound:
- slides set 2
- Ch 6 (review), Ch 7.1-7.2 (review), Ch 8.1

- divide and conquer:
- slides set 3
- boardwork on solving recurrences with master theorem and on
Strassen's matrix multiplication algorithm
- Ch 4.1-4.3 plus Fig 4.3 in Ch 4.4, Ch 28.2

- greedy algorithms:
- slides set 4
- boardwork on slightly different proof of optimality of Huffman codes
than in textbook
- Ch 16.2-16.3, Ch 23 (skip Prim's alg)

- dynamic programming:
- slides set 5
- boardwork on example execution to print best matrix chain order,
longest common subsequence algorithm, assembly line scheduling
algorithm, and Floyd-Warshall all-pairs-shortest-path algorithm
- Ch 15.1-15.4, Ch 25.2
- will not cover matroids

- amortized analysis:
- slides set 6
- boardwork on dynamic tables
- Ch 17

- disjoint sets:
- slides set 7
- Ch 21.1-21.3
- Skip Ch 21.4; slides give a different analysis, from 1st edition
of textbook

Also review:

Quizzes 1-6 and their solutions (given in class).
Homeworks 1-3 and their solutions (given in class).
The format of the exam will be some short answers and some
"work-out" problems.