CS85/185 (2A hour)
Lower Bounds in Computer Science
You Can't Do That
One of the key themes of CS39 was understanding what computers
You have probably seen at least one theorem of this type in CS25:
you cannot sort 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⟩. |
CS109 (10A hour)
Advanced Level
Theory of Computation
In CS39 we learned that the Turing Machine is a powerful abstraction
that helps us reason about computation. We used it to study
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,
Σ 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⟩. |