Algorithm Design and Analysis December 1, 2008Pennsylvania State University CSE 565, Fall 2008Adam Smith Handout 14Homework 11 – Due Friday, December 5, 2008Please refer to the general information handout for the full homework policy and options.Reminders• Your solutions are due before the lecture. Late homework will not b e acc epted.• Collaboration is permitted, but you must write the solutions by yourself without assistance,and be ready to explain them orally to a member of the course staff if asked. You must alsoidentify your collaborators. Getting solutions from outside sources such as the Web or studentsnot enrolled in the class is strictly forbidden.• To facilitate grading, pleas e write down your solution to each problem on a separate sheet ofpaper. Make sure to include all identifying information and your collaborators on each sheet.Your solutions to different problems will be graded separately, possibly by different people, andreturned to you independently of each other.• For problems that require you to provide an algorithm, you must give a precise description ofthe algorithm, together with a proof of correctness and an analysis of its running time.You may use algorithms from class as subroutines. You may also use any facts that we provedin class or from the bo ok.Reminder To show that a problem is NP-complete, you must show both that it is in NP and thatit is NP-hard. The easiest way to show that problem X is NP-hard is to prove Y ≤PX where Y isan NP-hard problem already covered in class.Exercises These should not b e handed in, but the material they cover may appear on exams:1. KT Chapter 8, Problems 1–6, 8, 13.Problems to be handed inPage limits: The answer to each problem should fit in 2 pages (or one double-sided sheet) ofpaper. Longer answers will be penalized.1. (Resource Reservation Problem) KT, Chapter 8, Problem 4.(It may help to also lo ok at KT, problem 2.)(See over.)12. (Search vs. Decision Problems) Let SAT be the decision problem defined on page 459 ofKT. Let SAT-SEARCH be the search version of the problem, where the input is a formula Ψand the goal is to output a satisfying assignment for Ψ if one exists. Show thatSAT-SEARCH ≤p,CookSAT.In other words, show how to solve SAT-SEARCH is polynomial time, given an oracle for SAT.(Hint: Figure out a good assignment for one variable at a time. Analyze the running time ofyour algorithm, its space complexity and the number of calls to the oracle. It may help to reviewthe self-reduction for vertex-cover seen in