One of the key themes of CS39 was understanding what computers cannot do. We studied the inabilities of finite automata, pushdown automata and Turing Machines. In this course, we continue this theme, moving into a more challenging domain: what can a computer not do if we limit a crucial resource? Equivalently, what lower bounds can we prove on the amount of resources required to solve a problem?

You have probably seen at least one theorem of this type in CS25: you cannot sort n numbers using fewer than n log n comparisons. This course will explore a number of results of this type.

The proofs will be very clever, almost like puzzle-solving. We won't need anything specific from CS25 or CS39, except for the maturity you gained from those courses. We will need a little linear algebra; all other math we use will be introduced in the course.

Are you ready for a course full of challenging puzzles?

Then check out the details at ⟨www.cs.dartmouth.edu/~cs85⟩.

In CS39 we learned that the Turing Machine is a powerful abstraction that helps us reason about computation. We used it to study efficient computation, building the classes P and NP. But just when the fun started, the term ended!

In this course, we shall continue from where CS39 left off, and delve deeper into the mysteries of the Turing Machine and study five key aspects of computation: time, space, nondeterminism, randomness and interaction. The goal is to understand the power of each of these. In the process, we shall create a slew of complexity classes to join our old friends P and NP. Here are some of them: L, NL, RL, BPP, coNP, Σ₂, Π₂, AM, PH, PSPACE. (Google "Complexity Zoo" if that made you curious.)

This course builds on top of machinery developed in CS39. Therefore, CS39 (or an equivalent course) is a critical prerequisite. We will also need elimentary probability theory; nothing more than what was covered in CS19.

Ready for a trip to the frontiers of knowledge in CS?

Then check out the details at ⟨www.cs.dartmouth.edu/~cs109⟩.