CompSci 161 Homework Assignments - Winter, 2012 (Dillencourt)

NOTE: Some suggestions about the preparation homework papers can be found here. This was prepared by Joe Simons, who was a Reader and a TA for several previous offerings of the course.

Please adhere to the following guidelines when you turn in your homework.

• Your homework should be legible, neat, coherent, concise, and complete. If the grader cannot read it with a reasonable amount of effort you may receive little or no credit, even it if is correct.
• Label each problem clearly.
• Make sure the following information appears at the top of each page, and that it is clearly visible and easily distinguishable:
  1. Your name (First Last) as you are officially registered. (So if your name is Frederic Bond and you use the nickname James, you should write "Frederic Bond" rather than "Bond, Frederic" or "James Bond.")
  2. Your student number
  3. CompSci 161 - Winter, 2012
  4. Homework # x (for the appropriate value of x).

Homework assignments are due at the start of lecture on the indicated day. The course homework policy is posted on the class web page.

• Homework 1: Due Wednesday January 18.
  • R-1.6; R-1.8; R-1.9; R-1.10; R-1.12; R-1.14; R-1.16; R-1.19
  • C-1.3; C-1.6; C-1.22; C-1.27; C-1.30.
• Homework 2: Due Wednesday January 25. Note all these problems are required, including the "additional problems."
  • R-2.3; R-2.9; R-3.2
  • C-4.4; C-4.5; C-4.9; C-4.10; C-4.11
  • Additional Problems
• Homework 3: Due Wednesday February 1. Note all these problems are required, including the "additional problems."
  • C-4.14; C-4.15; C-4.22; C-4.25 (On 4.25: answer in terms of average running time rather than worst case.)
  • Additional Problems
• Homework 4: Due Wednesday February 15. Note all these problems are required, including the "additional problems."
  • R-5.1; R-5.2; R-5.3; C-5.1; C-5.3; C-5.4; C-5.6
  • Additional Problems
• Homework 5: Due Wednesday February 22
  • Homework 5 Problems
• Homework 6: Due Wednesday February 29
  • R-6.1; R-6.2; R-6.3; R-6.4; R-6.6; R-6.10
  • C-6.6; C-6.9; C-6.12; C-6.18
• Homework 7: These problems will not be collected. THEY ARE STRONGLY RECOMMENDED AS PREPARATION FOR THE FINAL EXAM.
  Note: for some of these problems it may be possible to call one of the algorithms used in class as a subroutine (i.e., to reduce the assigned problem to a previously discussed problem.) To the extent that this is possible such a solution is preferred.
  • R-5.9; R-7.1; R-7.2; R-7.4; R-7.7; R-7.8; R-7.9
  • C-5.13; C_7.1; C-7.2; C-7.3; C-7.5; C-7.7; C-7.9.
  • Two additional problems:
    1. This problem is a variant of the change-making problem discussed in C-5.3 and C-5.4. Suppose you are given k coin denominations A[1]>A[2]>...>A[k]=1, and a value n. Describe an efficient dynamic programming programming algorithm to make change for n, using a minimum number of coins. State the running time of your algorithm in terms of n and k.
    2. You are given a DAG, with n vertices, such that each edge goes from a lower-numbered vertex to a higher-numbered vertex. Each edge has an associated edge weight. Describe an efficient dynamic programming algorithm for finding the longest path (i.e., path of highest total weight) from vertex 1 to vertex n. State the running time of your algorithm in terms of m and n, where m is the number of edges.

Last modified: March 12, 2012