![[Penguin+ Princeton logo]](penquin-shield.jpeg)
This objective in this course is to study two kinds of questions at a theoretical level. First, what computations can be performed on a computer? (This is the subject of computability theory .) Second, how efficiently can they be performed? (This is the subject of complexity theory .) These questions will ultimately be studied with respect to an idealized model of the computer, namely, the Turing machine. But we will start off by studying weaker models of computation: finite automata and grammars.
The issues studied in this course constitute the logical foundations of computer science. Time permitting, we will explore how they touch upon current areas of research, including AI, robotics, computer security and cryptography, and computation using quantum physics.
Both grads and undergrads are welcome to take the course. Some minimal level of mathematical sophistication will be assumed; COS 341 (or an equivalent course) is adequate preparation. 50% of the grade will be based upon assignments, which will be handed out every two weeks. There will also be a midterm exam and a final (possibly take-home).
The text will be Theory of Computation by Michael Sipser, printed by PWS publishing.
Instructor:
Sanjeev Arora. MW 3-4pm, or by appointment