##
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.