Fall 2003

Homework

- 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.
- Write clearly and legibly. Grading will be based on correctness,
clarity, and whether your solution is of the appropriate length.
- 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.
- Homework is always due at the
**beginning**of class.

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

- Ex. 34.1-1
- Ex. 34.1-4
- Ex. 34.1-6. Just do union and complement.
- Ex. 34.2-1
- Ex. 34.2-4. Just do union and complement
- Ex. 34.3-3
- Ex. 34.4-6
- Prob. 34-1
- 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).
- Ex. 35.1-5
- Ex. 35.2-2
- Prob. 35-1

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

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

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

- 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.
- Ex. 15.3-5
- Prob. 15-2
- Prob. 15-7
- Ex. 16.2-2
- Ex. 16.2-4
- Ex. 16.3-6
- Ex. 16.4-1
- Ex. 16.5-2
- Prob. 16-1