CS 4349-001: Advanced Algorithm Design and Analysis

Fall 2017

Homework #1

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.