CS 464/664 Assignment 3

Winter 2002

Due: Friday, March 8, 2002 (in class)

1. 7.4.3 (a)
2. 7.4.3 (b) (ii), (iii), (vi) and (viii)
3. 7.4.4
4. 7.4.5
5. 7.4.7 (this is a tricky question: if you use a reference, cite it and we will give you 80% of the marks. Otherwise, try it without using the reference).
6. 7.4.8
7. 7.4.17
8. 8.4.3
9. (Bonus for 464, Required for 664) Prove: If TIME(n) = NTIME(n) then TIME(f(n)) = NTIME(f(n)) for any proper complexity function f(n). (Hint: If you have a problem which requires time f(n), how do you make it appear linear). (Note: You can use the contrapositive form, if you wish, but I think that is harder than the form presented here).