CS 570 Analysis of Algorithms

Homework Assignments

• Homework #1 (Due Feb 20, 2006 before class):
  1. Exercise 2.1-3 (page 21)
  2. Exercise 2.2-2 (page 27)
  3. Problem 2-4 (page 39)
  4. Problem 3-3 (page 58)
• Homework #2 (Due March 8, 2006 before class):
  1. Exercise 3.1-1 (Page 50)
  2. Exercise 3.1-2 (Page 50)
  3. Exercise 3.1-4 (Page 50)
  4. Exercise 3.2-5 (Page 57)
  5. Problem 3-1 (Page 57)
  6. Exercise 4.1-3 (Page 67)
  7. Exercise 4.1-5 (Page 67)
  8. Exercise 4.2-4 (Page 72)
  9. Exercise 4.2-5 (Page 72)
  10. Exercise 4.3-1 (Page 75)
  11. Problem 4-6 (Page 87)
• Homework #3 (Due April 3, 2006 before class)
  1. Exercise 28.2-1 (page 741)
  2. Exercise 28.2-2 (page 741)
  3. Exercise 28.2-3 (page 741)
  4. Exercise 28.2-6 (page 741)
  5. Exercise 7.1-1 (page 148)
  6. Exercise 7.2-6 (page 153)
  7. Problem 7-2 (page 160)
  8. Problem 7-3 (page 161)
• Homework #4 (Due April 24, 2006 before class)
  1. Exercise 9.1-1 (page 185)
  2. Exercise 9.2-4 (page 189)
  3. Exercise 9.3-3 (page 192)
  4. Exercise 9.3-6 (page 192)
  5. Exercise 9.3-8 (page 193)
  6. Problem 9-2 (page 194)
• Homework #5 (Due May 3, 2006 before class)
  1. Ex 15.1-2 (p331) (change substitution to induction)
  2. Ex 15.1-4 (p331)
  3. Ex 15.1-5 (p331)
  4. Ex 15.2-1 (p338)
  5. Ex 15.2-4 (p338)
  6. Ex 15.3-3 (p349)
  7. Ex 15.3-5 (p350)
  8. Ex 15.4-1 (p355)
  9. Ex 15.4-2 (p356)
  10. (Extra Credit) Ex 15.4-6 (p356)
  

Readings

• Section 2.1, 2.2, 2.3
• Chapter 3
• Chapter 4
• Chapter 28.2
• Chapter 7
• Chapter 9
• Section 15.1, 15.2, 15.3, and 15.4
• Kleinberg & Tardos pages 272-278

Syllabus