CPSC 311: Review for Exam 2
Spring 2004

The exam is cumulative in the sense that you should remember the material we covered for the first exam. However, the focus will be on the material since then.

Review the following:

• Lectures on 2/25 (dynamic programming) through 4/12 (Floyd-Warshall APSP algorithm)

• Readings: Chs 15.1-15.4, 21.1-12.3, 22.1-22.4, 23, 24.1-24.3, 25.1-25.2.

• Quizzes 7-10 and their solutions (given in class).

• Homeworks 4-6 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:

• The dynamic programming paradigm (general approach).
  DP solutions (recursive formulation, order of computing subproblems, time and space) for
  • Fibonacci numbers
  • matrix chain order
  • longest common subsequence

• Here is another practice problem for dynamic programming: You are given a set of n items of different sizes; the i-th item has size s_i (the size is a positive integer). You are also given an integer K. You are to find a subset of the items whose sizes sum to exactly K; if there is no such subset, then report that fact.
  Hint: Let C[i,m] be the solution to the subproblem when only items 1 through i are considered and the sizes should sum to m.

• Specification of disjoint set ADT.
  Implementations of disjoint set ADT:
  • Linked-list implementation (with and without weighted union). Running time for a sequence of operations, and why.
  • Forest implementation (with union by rank and path compression). Running time for a sequence of operations (don't need to know the proof).
  Some applications of disjoint set ADT (graph algorithms).

• Basic graph definitions. Adjacency list representation and adjacency matrix representation and their pros and cons.

• Know the following graph algorithms:
  • breadth-first search
  • depth-first search
  • topological sort (application of DFS)
  • Kruskal's minimum spanning tree (uses disjoint-set data structure)
  • Prim's minimum spanning tree (uses priority queue data structure)
  • Dijkstra's single source shortest path (uses priority queue)
  • Bellman-Ford's single source shortest path
  • Floyd-Warshall's all pairs shortest path (uses adjacency matrix)

  For each of the above algorithms, you should know:

  • how the algorithm works, so that you could compute the output of running the algorithm on a given graph
  • the time and space requirements, as functions of both V and E, and why. Be able to specialize the time and space formulas for specific values of E (e.g., sparse graphs vs. dense graphs).