Homeworks - CSCI 570, Fall 2013, Both Sections

Homeworks - CSCI 570, Fall 2013, Both Sections

Written homeworks will not be collected or graded. They will be problems from the required textbook (Kleinberg & Tardos). You are expected to work on them since exam questions may resemble these problems!

There are no programming assignments.

Written Homework Assignments

On all the written homework assignments, when you are asked to give an algorithm, in addition to the algorithm, you must also give (a) a proof of its correctness and (b) an analysis of its complexity.

All homework assignments are from Kleinberg and Tardos, 1st edition, unless otherwise stated.

Chapter 1 (Representative Problems): Read Chapter 1. Problems 1, 2, and 7. [solutions]
Chapter 2 (Algorithm Analysis): Read Chapter 2. Problems 3, 5, and 6(a,b). [solutions]
Chapter 3 (Graphs): Read Chapter 3. Problems 2, 3, and 12. [solutions]
- In addition, give a rigorous mathematical proof by contradiction for the claim on slide 35 of Lecture 9 on Sep 24, 2013. [solutions]
Chapter 4 (Greedy Algorithms): Read Chapter 4. Problems 3, 7, 17, and 28. [solutions]
Chapter 5 (Divide and Conquer): Read Chapter 5. Problems 2 and 3. [solutions]
Chapter 6 (Dynamic Programming): Read Chapter 6. Problems 1, 5, 10, and 20. [solutions]
Chapter 7 (Network Flow): Read Chapter 7. Problems 7, 12, 16, and 29. [solutions]