Expect 4-5 questions.  Answer all.  Topics include 
recurrence relation, divide-and-conquer, dynamic programming,
greedy and graph algorithms.


Look at practice questions for midterm1 and 2 for problems in
recurrence relation, dynamic programming and greedy algorithms.

For graph algorithms:

1. Problem 22.1-5  page 530

2. Problem 22.1-6  page 530

3. Problem 22.2-6  page 539

4. Problem 22.2-7  page 539

5. Problem 22.2-8  page 539

6. Problem 22.3-12 page 549

7. Problem 22.5-7  page 557

8. Problem 24.3-4  page 600

9. Problem 24.3-8  page 601

10.  Suppose you are given weighted directed graph with NO negative
cycles.  But the weights may be negative.  Can we apply Dijkstra's
shortest path algorithm?  Why or why not?

11.  Suppose you are given weighted direced graph G with NO negative
cycles.  But weights may be negative.  

Let -W be the smallest negative weight. (Suppose
-4, -5, -7 are the only negative weights then -W = -7, the smallest negative weight).
Now update the weight of each edge by adding W.  You get a new
weighted graph with no negative weight.  If I find the shortest
path on the new graph, will it be the shortest path in the
original graph?


Try to solve problems.  Unless you try and prepare, no matter how easy
the questions are, you will find them to be difficult.  

Feel free to stop by and ask questions.