# Midterm exam – Thr. October 31, 2013

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