CS 4349-001: Advanced Algorithm Design and Analysis

Fall 2017

Homework #2

Thursday, September 14, 2017

Due date: Thursday, September 28, 2017



1. Problem 9.3-7, page 223 (20 points).


2. Problem 9-2, only a,b,c, page 225 (20 points).


3. Problem 33.4-1, page 1043 (20 points).


4. Problem 33.3, page 1045 (20 points).


5. Let P be a set of n points in the plane. Prove that the farthest pair of points in P is achieved by two vertices of the convex hull of P (20 points).



Note: thoroughly justify all your answers.