CPSC 629
Fall 2003
Homework
General Instructions:
- 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.
Homework 6. Due 2:20 PM, Tuesday, Dec. 9, 2003.
Contact me if this deadline is a problem for you.
- Ex. 32.2-2. Assume that all k patterns have the same length.
- Ex. 31.7-1
- Prob. 31-1
- Prob. 31-3
Homework 5. Due 2:20 PM, Tuesday, Dec. 2, 2003.
Do not wait until Thanksgiving vacation to start this!!!
- 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
Homework 4. Due 2:20 PM, Tuesday, Nov. 11, 2003
- 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)
Homework 3. Due 2:20 PM, Tuesday, Oct. 21, 2003
- 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
Homework 2. Due 2:20 PM, Thursday, Oct. 2, 2003
- 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
Homework 1. Due 2:20 PM, Thursday, Sept. 18, 2003
- 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