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:
- 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.")
- Your student number
- CompSci 161 - Winter, 2012
- Homework # x (for the appropriate value of x).
Unless otherwise stated, all problems are from [GT].
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."
- 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."
- Homework 5: Due Wednesday February 22
- 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:
- 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.
-
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