Learning Outcomes versus Collected Course Materials
| LO1 | LO2 | LO3 | LO4 | LO5 | LO6 | LO7 | N/A |
HW1 | X | | | | | | | X |
HW2 | X | X | | | | X | | |
HW3 | | X | X | | X | | | |
HW4 | | | X | X | | | | |
HW5 | | | | | X | X | X | |
MT1Prob1 | | | | | | | | X |
MT1Prob2 | X | | | | | | | |
MT1Prob3 | X | | | | | | | |
MT1Prob4 | | | | | | X | | |
MT1Prob5 | | X | | | | | | |
MT2Prob1 | | | X | | | | | |
MT2Prob2 | | | | | X | | | |
MT2Prob3 | | | | X | | | | |
MT2Prob4 | | X | | | | | | |
MT2Prob5 | | | | | X | | | |
FinProb1 | X | | | | | | | |
FinProb2 | | X | | | | | | |
FinProb3 | | | X | | | | | |
FinProb4 | | | | | X | | | |
FinProb5 | | | | | X | | X | |
FinProb6 | | | | | | | X | |
FinProb7 | | | | X | | | | |
FinProb8 | | | | | X | | | |
FinProb9 | | | | | | X | | |
FinProb10 | | | | | | X | | |
Within the class there were
two versions of a given test; however, these two versions were just problem permutations
of each other. The results above are all for the first of these two permutations.
LO1 (Learning Outcome 1) -- Exhibit a simulation of one machine model with another. For instance, a Turing
machine by a RAM.
LO2 -- Give a minimal classification of the complexity of a computational problem as being in one of the class
L, P, 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.
LO4 -- Know properties of the randomized classes RP, BPP.
LO5 -- Know conditions under which various of these hierarchies might collapse.
LO6 -- Explain at least one circuit lower bound technique such as Razborov's techniques for monotone circuits.
LO7 -- Exhibit a relativized separation (oracle result) of complexity classes for standard classes such as P and
NP.
N/A -- Important material covered in the course but not directly related to a specific learning outcome.
|