Assignments in Computer Algorithms (Spring 2014)

This page lists all the Reading Assignments and Homeworks for Computer Algorithms. Please remember to put your name on each problem, as well as the names of your collaborators. For homework policies, see the 4020 Homework Guide.

*Reading Assignment:* Read Ch.1, and study for the Quiz on Jan 27th by reading Ch.2, 3, and the Discrete Math handout, as well as trying to solve all the problems.

**Problem Set 1:** Due Thursday, Feb 6th, at the beginning of class. Solve problems **3.10 and 4.7.** That is, solve problem 10 from Chapter 3, and problem 7 from Chapter 4 of the textbook.

Solutions can be picked up during my office hours, or in class. The most common incorrect solution for 3.10 was counting the number of neighboring nodes in the previous layer that each node has, instead of the total number of paths going through those nodes. See the solutions for common mistakes on problem 4.7.

*Reading Assignment:* Read Sections 4.2, 4.4-4.5, 4.7.

**Problem Set 2:** Due Thursday, Feb 13th, at the beginning of class. Solve problems **19 and 21** from Chapter 4 of the textbook. You may assume that edge bandwidths are *distinct* in Problem 19.

*Reading Assignment:* Read Sections 6.1-6.4.

**Problem Set 3:** Due Thursday, Feb 20th, at the beginning of class. Solve problems **3 and 6** from Chapter 6 of the textbook. See Writing Up Dynamic Programming Solutions for what is typically expected from a description of a dynamic programming algorithm.

*Reading Assignment:* Read Section 6.5-6.8.

**Problem Set 4:** Due Thursday, Feb 27th, at the beginning of class. Solve problems **15 and 20** from Chapter 6 of the textbook. See Writing Up Dynamic Programming Solutions for what is typically expected from a description of a dynamic programming algorithm.

See the TA comments and common mistakes for PS4. Solutions can be picked up during my office hours, or in class.

*Reading Assignment:* Read Sections 5.1-5.6.

**Problem Set 5:** Due Thursday, Mar 20th, at the beginning of class. Solve problem **28** from Chapter 6 of the textbook. Since this problem set consists of only a single homework problem, it will be worth 1/2 as much as the others. Notice that you have 3 weeks to do this assignment because of the Midterm Exam and Spring Break.

*Reading Assignment:* Read Sections 7.1-7.2, 7.5-7.6.

**Problem Set 6:** Due Thursday, Mar 27th, at the beginning of class. Solve problems **7 and 15** from Chapter 7 of the textbook.

*Reading Assignment:* Read Sections 7.7-7.9.

**Problem Set 7:** Due Thursday, Apr 10th, at the beginning of class. Solve problems **19 and 34** from Chapter 7 of the textbook.

*Reading Assignment:* Read Sections 7.10-7.11.

**Problem Set 8:** Due Thursday, Apr 17th, at the beginning of class. Solve problems **7.45 and 8.14** (that is, Problem 45 from Chapter 7, and Problem 14 from Chapter 8). For problem 8.14, to show that the problem is NP-complete, begin by proving that it is harder than one of: Vertex Cover, Set Cover, Independent Set, 3-SAT. Then show that the problem is in NP.

See the TA comments and common mistakes for PS8. Solutions can be picked up during my office hours, or in class.

*Reading Assignment:* Read Sections 8.1-8.8.

**Problem Set 9:** Due Monday, Apr 28th, at the beginning of class. Solve problems **20 and 24** from Chapter 8 of the textbook. Notice that this homework is due on a Monday.

*Reading Assignment:* Read Sections 10.1-10.2, 11.1-11.6, 11.8.