CS141 Lab 8

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

For the labs of the eighth week:

• Go over the  third homework.

• Answer remaining questions regarding the  second programming assignment.

• Give an additional example of Floyd's algorithm for all-pairs shortest paths and Warshall's algorithm for the transitive closure (using e.g. Figure 25.4 in CLRS or Ex. 25.2-1 but ignoring vertices 3 and 6), if there is sufficient interest from the students. Observe that negative weights do not cause any problem for these algorithms.

• In-lab exercise: Implement the dynamic programming algorithm for Knapsack in C++. Test it on some random input data. Output the final T/F result for for each test data set.

TA: Provide some test data with the correct T/F anwsers. Keep track of which students completed the exercise and encourage the rest to complete the exercise at home.

• For keen students: Write an O(VE)-time algorithm to compute the transitive of an input digraph G = (V,E), assuming that G is represented as adjacency lists. It would also be a good exercise to implement the algorithm in C++ by possibly recycling some code from Lab 6.