CPSC 311: Analysis of Algorithms
Information and Review Questions for Exam 3
Spring 2003

General Information

The third exam will be during the final exam times, which are different for the two sections:

It will cover material from Chapters 24, 25, 15, 34, and 35 in the text. It will be a closed book exam (no notes, books, or neighbors) except you will be allowed a one page, two side cheat sheet which must be turned in with the exam. There will be 5 questions worth a total of 100 points. Remember to show your work - partial credit will be given.

Material

All of the following are considered to be fair game:

Review Questions

Below are some suggested review exercises/problems for the exam. It is strongly recommended that you be able to do all of these problems. Solutions will not be handed out. Finally, be sure to check your email -- clarifications and/or explanations will be mailed to the class if needed.

  1. Study Homeworks #8-10 and Quizzes 9-11; variations of some of these questions will appear on the exam.

  2. Shortest Paths (Chapt 24, 25): Know Dijkstra's single-source shortest path (SSSP) algorithm and the Floyd-Warshall all-pairs shortest paths (APSP) algorithm. Know their running times, and when they can and cannot be applied.

    Give a simple example of a directed graph with negative weight edges for which Dijkstra's algorithm produces incorrect answers. Use this example to explain why the proof of correctness for Dijkstra's algorithm doesn't go through when negative weight edges are allowed.

    In some cases, one can solve the APSP problem using V applications of Dijkstra's algorithm (one for each node of G). Give a simple example of a case when this won't work, but when the Floyd-Warshall algorithm can be used to solve the APSP problem correctly.

  3. Dynamic Programming (Chapt 15): Study the dynamic programming technique. Know when it would be a good solution technique and when it would not. Study the dynamic programming applications we covered in class (Floyd-Warshall and matrix multiplication order), or in homework (e.g., problem 15-6 in the text).

  4. Dynamic Programming (Chapt 15): A carpenter has a piece of wood of a certain length that must be cut at positions a1, a2 ..., an where ai is the distance from the left end of the original piece of wood. Notice that after making the first cut, the carpenter now has two pieces of wood; after making the second cut, the carpenter has three pieces of wood, etc. Assume that the cost of making a cut in a piece of wood of length l is equal to l, and is the same no matter which position in that piece of wood is being cut. Let L be the length of the original piece of wood.

    First, derive the recurrence relation which could be used to design a recursive algorithm to find the minimum total cost for making all the cuts.

    Second, describe a top-down recursive dynamic programming algorithm to find the minimum total cost for making all the cuts that minimizes the total cost. Analyze the worst-case running time and storage requirements of your algorithm.

    Third, describe a bottom-up recursive dynamic programming algorithm to find the minimum total cost for making all the cuts adn the order in which to make the cuts that minimizes the total cost. Analyze the worst-case running time and storage requirements of your algorithm.

  5. NP-Completeness and Approximation Algorithms (Chapt 34, 35): Know and understand definitions of the classes P, NP, NP-Complete. Know and understand what it means for one problem to be transformable to another problem in polynomial time. Know and understand how you would prove that a problem is NP-Complete (using polynomial time transformations). Know what an approximation algorithm is, and when one might be useful.

  6. NP-Completeness and Approximation Algorithms (Chapt 34, 35):

    The Hamiltonian Path (HP) problem is, given an undirected graph G=(V,E), does there exist a path in the graph that visits every node in V exactly once?

    The Hamiltonian Circuit (HC) problem is, given an undirected graph G=(V,E), does there exist a cycle in the graph that visits every node in V exactly once?

    The Longest Circuit (LC) problem is, given a weighted undirected graph G=(V,E) and a bound B, does there exist a cycle in G whose weight is at least B?

  7. NP-Completeness and Approximation Algorithms (Chapt 34, 35): Consider the following three problems (defined in class and in the text): Independent Set (IS), Vertex Cover (VC), Clique.