CompSci 161 Homework Assigments - Spring, 2008 (Dillencourt)

Homework assignments will be posted to this page. Homework assignments are due at the date and time indicated at the ICS Distribution Center. Late homework will not be accepted.

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 - Spring, 2008
4. Homework # x (for the appropriate value of x).

Unless otherwise stated, all problems are from [GT].

Problems to be discussed on April 2 and April 7. These will not be collected or graded, but you should still do them.
- R-1.2; R-1.4; R-1.10; R-1.12; R-1.14; R-1.15; R-1.19;
- C-1.4; C-1.17;
Homework 1: Due on or before Wednesday April 9, 1:45PM, in the ICS Distribution Center
- R-1.6; R-1.8; R-1.9; R-1.16;
- C-1.3; C-1.6; C-1.22; C-1.27; C-1.30.
Homework 2: Due on or before Wednesday April 16, 1:45PM, in the ICS Distribution Center. Note that the "R" problems are from chapter 2 and the "C" problems from chapter 4.
- R-2.3; R-2.9; R-2.11 (answer for both max-heap and min-heap); R-2.13.
- C-4-2; C-4-4; C-4.9; C-4.10.
Homework 3: Due on or before Wednesday April 23, 1:45PM, in the ICS Distribution Center.
- R-5.1; R-5.2; R-5.3
- C-4-14; C-4-15; C-5.2; C-5.3; C-5.4
Homework 4: Due on or before Wednesday May 7, 1:45PM, in the ICS Distribution Center. Click here.
Homework 5: Due on or before Wednesday May 14, 1:45PM, in the ICS Distribution Center. Click here.
Homework 6: Due on or before Wednesday May 21, 1:45PM, in the ICS Distribution Center.
- R-6.1; R-6.2; R-6.3; R-6.6; R-6.10
- C-6.6; C-6.9; C-6.12; C-6.18
- Is the converse of the statement in C-6.6 true? In other words, is the following statement true?
  - If a graph G has at least 3 vertices, then it has a separation vertex only if it has a separation edge.
  Justify your answer.
Homework 7: Due on or before Wednesday June 4, 1:45PM, in the ICS Distribution Center.
- R-7.2; C-7.1; C-7.2; C-7.3; C-7.5; C-7.7; C-7.9
- Additional Recommended problems (not to be handed in): R-7.1; R-7.4; R-7.6; R-7.7; R-7.8; R-7.9. (Also: find the grammar error in the statement of problem C-7.1.)
Homework 8: These are recommended problems, not to be turned in. I will post solutions before the final exam.
- 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 values: 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: June 5, 2008