CPSC 629
Fall 2003
Homework

General Instructions:
1. The numbers refer to the [CLRS] textbook. Don't get confused between Exercises, at the end of each section, and Problems, at the end of each Chapter.

2. Write clearly and legibly. Grading will be based on correctness, clarity, and whether your solution is of the appropriate length.

3. Turn in an assignment cover page with each homework assignment. Don't forget to acknowledge all sources of assistance. Unless otherwise instructed, you must write up your homework on your own.

4. Homework is always due at the beginning of class.

Homework 6. Due 2:20 PM, Tuesday, Dec. 9, 2003. Contact me if this deadline is a problem for you.

1. Ex. 32.2-2. Assume that all k patterns have the same length.
2. Ex. 31.7-1
3. Prob. 31-1
4. Prob. 31-3

Homework 5. Due 2:20 PM, Tuesday, Dec. 2, 2003. Do not wait until Thanksgiving vacation to start this!!!

1. Ex. 34.1-1
2. Ex. 34.1-4
3. Ex. 34.1-6. Just do union and complement.
4. Ex. 34.2-1
5. Ex. 34.2-4. Just do union and complement
6. Ex. 34.3-3
7. Ex. 34.4-6
8. Prob. 34-1
9. Read Prob. 34-3. Show 3-COLOR is NP-complete using the reduction described in the problem. You do not need to follow exactly the proof outline specified by parts (d)-(f).
10. Ex. 35.1-5
11. Ex. 35.2-2
12. Prob. 35-1

Homework 4. Due 2:20 PM, Tuesday, Nov. 11, 2003

1. Ex. 24.3-4
2. Ex. 24.3-6
3. Prob. 24-1
4. Ex. 25.2-6
5. Prob. 25-2 (don't forget part (d) on the next page). ** corrected 11/6, used to refer to nonexistent part (f) **
6. Ex. 26.1-9
7. Ex. 26.2-9
8. Prob. 26-3 (don't forget part (c) on the next page).
9. Prob. 26-4, part (a)

Homework 3. Due 2:20 PM, Tuesday, Oct. 21, 2003

1. Ex. 19.2-2. You should do it, but it won't be graded.
2. Ex. 19.2-3. You should do it, but it won't be graded.
3. Ex. 19.2-10
4. Prob. 19-1
5. Ex. 20.2-1. You should do it, but it won't be graded.
6. Ex. 20.2-3
7. Ex. 20.2-5
8. Prob. 20-2, part (a).
9. Ex. 21.4-2
10. Ex. 21.4-4
11. Prob. 21-2

Homework 2. Due 2:20 PM, Thursday, Oct. 2, 2003

1. Ex. 17.1-3
2. Ex. 17.2-2
3. Ex. 17.3-2
4. Ex. 17.3-3
5. Ex. 17.4-3
6. Prob. 17-2
7. Prob. 17-3
8. Ex. 18.2-1. You should do it, but it won't be graded.
9. Ex. 18.2-6 (remember that "lg" means "log base 2")
10. Ex. 18.3-1. You should do it, but it won't be graded.
11. Prob. 18-2

Homework 1. Due 2:20 PM, Thursday, Sept. 18, 2003

1. Consider a generalization of the assembly line scheduling problem in which there are k assembly lines, instead of 2. Describe a dynamic programming solution to the problem and analyze its running time. Your expression for the running time should include k as a parameter.
2. Ex. 15.3-5
3. Prob. 15-2
4. Prob. 15-7
5. Ex. 16.2-2
6. Ex. 16.2-4
7. Ex. 16.3-6
8. Ex. 16.4-1
9. Ex. 16.5-2
10. Prob. 16-1