CS141 Lab 9

Class Webpage:  http://www.cs.ucr.edu/~jiang/141-homepage.html

For the labs of the ninth week:

• Go over the  second programming assignment solutions. The tests and results can be found in Lab 7.

• Give an additional example of Dijkstras' algorithm, if there is sufficient interest from the students.

• Go over Ex. 24.3-2 on CLRS, p. 600. Explain why the algorithm does not work when negative weights are present.

• In-lab exercise: Write an efficient algorithm to find an MST for an input (connected) graph with edges of weights that are either 1 or 2. What is the running time of your algorithm? How should the graph be represented?

TA: Keep track of which students completed the exercise.

• For keen students: 

  Implement your algorithm in C++. Again, assume that the vertices are labeled with integers 1 through n. You may use some of your codes from Lab 6 (with appropriate modifications).

• For keen students who love proofs:

  Can you prove that the greedy coin-changing algorithm is optimal for coins {1, 5, 10, 25}?