CS 4349-001: Advanced Algorithm Design and Analysis
Due date: Thursday, September 14, 2017
1. Problem 2-1, pag. 39 (20 points)
2. Problem 4.1-5, pag. 75 (20 points)
3. Problem 4.4-8, pag. 93 (20 points)
4. Problem 4.5-1, pag. 96 (20 points)
5. The maximum subarray problem asks to find a contiguous subset (of an array A of numbers) that
has the maximum (i.e., largest) sum. How about also finding the 2nd largest sum? Or the 1st, 2nd, and 3rd
largest sums? Give a divide-and-conquer algorithm to find the 1st, 2nd, and 3rd largest sums of an array A of
n numbers. Try to make your algorithm as fast as possible. (20 points)
Note: thoroughly justify all your answers.
Note: the numbering (chapter, page and problem
numbers) in the third edition of textbook is not the same as in the second
edition. Use the third edition.
Note: The homework should be uploaded in eLearning by due date.