Assignments in Computer Algorithms (Spring 2016)

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 29th by reading Ch.2, 3, and the Discrete Math handout, as well as trying to solve all the problems.

**Problem Set 1:** Due Friday, Feb 12th, at the beginning of class. Solve problems **3.7 and 4.6.** That is, solve problem 7 from Chapter 3, and problem 6 from Chapter 4 of the textbook.

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

**Problem Set 2:** Due Friday, Feb 19th, at the beginning of class. Solve problems **4.9 and 6.2.** That is, solve problem 9 from Chapter 4, and problem 2 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 Sections 6.1-6.2.

**Problem Set 3:** Due Friday, Feb 26th, at the beginning of class. Solve problems **7 and 8** 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.3-6.4.

**Problem Set 4:** Due Friday, Mar 6th, at the beginning of class. Solve problems **19 and 26** 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.

*Reading Assignment:* Read Sections 5.1-5.6.

**Problem Set 5:** Due Friday, Mar 25th, at the beginning of class. Solve problem **22** 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.

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

**Problem Set 6:** Due Friday, Apr 1st, at the beginning of class. Solve problems **6 and 12** from Chapter 7 of the textbook.

*Reading Assignment:* Read Sections 7.7-7.9.

**Problem Set 7:** Due Friday, Apr 15th, at the beginning of class. Solve problems **20 and 41** from Chapter 7 of the textbook. Notice that you have 2 weeks to do this assignment.

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

*Reading Assignment:* Read Sections 7.10-7.11.

**Problem Set 8:** Due Friday, Apr 22nd, at the beginning of class. Solve problems **7.44 and 8.4** (that is, Problem 44 from Chapter 7, and Problem 4 from Chapter 8). For problem 8.4, 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.

*Reading Assignment:* Read Sections 8.1-8.8.

**Problem Set 9:** Due Tuesday, May 3rd, at the beginning of class. Solve problems **10 and 17** from Chapter 8 of the textbook. Notice that this homework is due on a Tuesday.

TA Comment 1: There needs to be an edge (j, 0) with weight -W for all j >= 1, not just (n, 0). If you don't have these edges, this forces every subset sum to take the number w_n.

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