Assignments in Computer Algorithms (Spring 2018)

This page lists all the Reading Assignments and Homeworks for Computer Algorithms. Homework should be handed in with each problem on a ** separate sheet of paper ** (since they will be handled separately during the grading). 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 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 2, at the beginning of class. Solve problems **3.4 and 4.7.** That is, solve problem 4 from Chapter 3 (Graphs), and problem 7 from Chapter 4 (Greedy Algorithms) of the textbook. Remember that you should always turn in each problem on a separate sheet of paper.

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

**Problem Set 2:** Due Friday, Feb 9th, at the beginning of class. Solve problems **4.20 and 6.4.** That is, solve problem 20 from Chapter 4 (Greedy Algorithms), and problem 4 from Chapter 6 (Dynamic Programming) 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 16th, at the beginning of class. Solve problems **6 and 9** 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.3-6.4.

**Problem Set 4:** Due Friday, Feb 23, at the beginning of class. Solve problems **16 and 24** 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.5-6.8.

**Problem Set 5:** Due Friday, Mar 23, at the beginning of class. Solve problems **9 and 14** from Chapter 7 (Network Flow) of the textbook. Notice that you have 2 weeks to do this assignment.

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

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

*Reading Assignment:* Read Sections 7.7-7.9.

**Problem Set 7:** Due Friday, Apr 13th, at the beginning of class. Solve problems **7.29 and 8.9** (that is, Problem 29 from Chapter 7, and Problem 9 from Chapter 8). For problem 8.9, 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 7.10-7.11, 8.1-8.5.

*Reading Assignment:* Read Sections 8.7-8.8.

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

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