HW#2 --- last modified February 10 2019 21:57:12..
Solution set.
Due date: Sep 28
Files to be submitted:
Hw2.zip
Purpose:To learn about which kinds of problems can be
classified as `P` versus can be classified as `NP`. To show some problems are `NP`-complete.
Related Course Outcomes:
The main course outcomes covered by this assignment are:
LO2 -- Give a minimal classification of the complexity of a computational problem as being in one of the class L, NL, P, P/poly, NP, coNP, some level of the polynomial hierarchy, PSPACE, E, EXPTIME, decidable, undecidable.
LO3 -- Show the completeness of a complete problem for each of these classes.
Specification:
Do the following problems out of A & B: 1.14, 2.2, 2.16, 2.22, 2.32.
On the day your homework is due I will ask each group to present one problem to me in class.
If you scored above 8 on Hw1 and you work for Hw2 with someone who scored below 8 on Hw1, I will give you a 1pt bonus. Similarly, if you scored below 8 on Hw1 and you work for Hw2 with someone who scored above 8 on Hw1, I will give you a 1pt bonus. Be advised though that all group members must be prepared to answer any question on class presentation day.
Point Breakdown
Five problems above (1.5 pts each - 1.5pts, completely correct; 1pt, missing minor details, 0.5pt, on the right track; 0 confused or wrong. |
7.5pts
|
Class presentation (Write-up clear, 1.5pts; all group members could answer brief questions about the problem intelligently, 1pt). |
2.5pts
|
Total | 10pts |
|