| Category | Difficulty |
|---|---|
| HW | 5 |
| Exams | 4 |
This class is an introduction to complexity theory, a domain in computer science theory. It is to be taken after 15-251, and focuses on calculating how much of a resource (time, space, etc.) is needed to solve a certain problem. The first half of UCT is a general overview (plus some new material) of material from 251, and the second half of UCT introduces many new complexity classes, and also talks about space as a resource.
- Homework: There is a weekly problem set consisting of 4 questions. The problems in UCT are overarchingly the same: present an algorithm/reduction, prove correctness (iff), and prove time and/or space complexity. There's a little bit of turing machine programming during the first few homeworks, but everything else is written (typed). Make sure you're comfortable with LaTeX!
- Exams: The exams are 1.5 hours long in class. They are fairly straightforward, with the problems being a little easier than the ones from homework.
- Read the notes!! Like any proof/algorithm class, you really need to know your definitions (I'd say even more for UCT, since there are so many complexity classes with their own definitions)
- The exam practice problems are not a great indicator of the exam. Oftentimes they're too hard or too weird (not like most homework problems) to appear in an actual exam. Your best bet for exams is reading the notes and going over the homework problems.
- Professor O'Donnell is really nice, but his office hours can be a little slow and filled with silence.
- The material is fairly boring the first half of the semester, since it's mostly review from 251 (Turing Machines, P, NP). However, after Midterm 1 concepts almost all the content is new, and is significantly more work than the first half of the semester if you've been slacking off.