CS141 Lab 4

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

For the labs of the fourth week:

• Go over the  second homework.

• Address questions concerning the first programming assignment. Go over the sample output for tests 1 through 3 and the sample C++ code for reading an input file.

• Introduce the Traveling Salesman Problem (TSP) and Knapsack Problem as defined in Levitin Ch 3.4. Give exhaustive search solutions for them and demonstrate why these solutions are not acceptable in practice.

• Give some examples to compare Mergesort and Quicksort. Review the worst-case time complexity analyses of them and explain why Quicksort is not as fast one might think, and why we terminate recursion in Quicksort early (e.g. when array size reaches 50) and switch to insertion sort.

• In-lab exercise: Implement Mergesort in C++.

TA: Provide some simple test data files. Keep track of which students completed the exercise.

• For keen students:

  Analyze the average-case complexity of Quicksort. The details are given in CLRS.

• An alternative exercise for keen students:

  Write an exhaustive search algorithm for the famous Wolf, Goat, and Cabbage puzzle, which is also the cover illustration of our textbook.