CPSC 411: Review for Exam 1
Fall 2008

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