Test 3 Review

• You'll be given any necessary reference material such as algorithms from the text or notes, definitions of W, Q, O and summation formulas.

• You can bring one page of notes on the front and back of an 8.5x11 inch paper and a calculator.

• No cell phones. Please plan to disable your cell phone during the test and make arrangements accordingly.
   

• Old Test 3
   

• Chapter 15 - Dynamic programming.
  1. Be familiar dynamic programming substructure.
      
• Chapter 16 - Greedy Algorithms

1. Be familiar greedy substructure.

• Chapter 21 - Disjoint sets.

1. Be familiar with array and linked list representations of disjoint sets.
2. Be familiar with path compression.
3. Be able to generate results for Make-Set, Union and Find-Set operations.

• Chapter 22
  1. Be familiar with representations of directed and undirected graphs (e.g. adjacency list and matrix).
  2. Be familiar with representations of directed and undirected graphs weighted graphs.
  3. Be able to generate results for BFS, DFS, Topological Sort, SCC operations.
      
• Chapter 24
  1. Be able to generate results for Single-Source Shortest Paths (cyclic and acyclic graphs) and Dÿkstra's algorithms.
      
• Backtracking and Best-first
  1. Be able to generate results from a backtracking algorithm.
  2. Be able to generate results for best-first given a lower-bound.
      
• Chapter 34 – NP Completeness
  1. Given a problem, e.g., HAM-CYCLE, show that it is satisfiable or unsatisfiable.
  2. Given a problem e.g., HAM-CYCLE, show that it belongs in the class NP