Happy Haloween!
Exam duration: 75 minutes, in class, on Thr. Oct 31, 2013.
Exam preparation guidelines:
- Chapters covered: 1, 2 (excluding section 2.6); 3.1
- Review linear programming
- Attempt the following exercises from the text: 1.1 (use the greedy algorithm), 1.2 (use the unweighted set cover problem); 1.6a; 2.1 – 2.4a; 2.5 (first convince yourselves that the MST on $G[R]$ is not optimal for the Steiner tree problem; then consider an optimal Steiner tree solution, make the tree Eulerian, and shortcut all the non-terminal vertices. What do you get?); 2.6; 2.11a; 2.16; 3.1, 3.2