Complete Problems 16 and 29 on pages 415-430 andProblems 2 and 19 on pages 505-515 inAlgorithm Design byKleinberg andTardosRequirements:

1. Answer in text must be typed. Graph may be drawn by hand and then scanned in. All in one PDF file to upload, with your name in the file name.
2. If you model a problem as a network-flow problem or its extension:
   1. Describe whatthe nodes, edges, capacities, source, sink represent and any necessary information.
   2. Describe how the solution to the (extended) network-flow problem may be interpreted as a solution to the original problem.
   3. If you use any standard algorithm (such as max-flow, augmenting path) presented in Chapter 7, you do NOT need to describe the details of the algorithm, but you need analyze the time complexity of this algorithm in the context of this specific problem you are solving here, such as what n means and what m means.
3. When present an algorithm:
   1. First describe the overall idea of the algorithm using English language.
   2. Then present the algorithm details using pseudo code, be clear of the meaning of each variable, with comments on important steps to explain its purpose.
   3. Mustwalk through the algorithm step by step with a small problem instance to show how the algorithm works. (Required, unless you have implemented the algorithm and show the output instead).
   4. Analyze time complexity of algorithm and present results in big-O notation.
4. To show a given problem is NP-Complete, follow the general three-step strategy on page 473.
   1. To prove a problem X is NP is to show there is an efficient certifier for X, which means, there is a polynomial time algorithm to check if s is a solution to X or not. (Page 464 – 465)
   2. To show problem Y is polynomial-time reducible to X, following the outline described in the middle of Page 473. Besides general description of the transformation, construct a concrete small problem instance of X and show how it is transformed to a problem instance of Y and how the answers to these two problem instances are related.

 

 

Hint:

 

• Chapter 7,Problems 16: refers to solved exercise 2 in chapter 7.
• Chapter 7,Problems 29: refers to the image segmentation problem.

can you please assign to @Yaman