Course Outline

Is a given problem solvable by computers? If so, how much time (or memory) do we need to solve it? Can a solution be obtained in a practically feasible manner? Is your desktop computer more powerful than your wristwatch? These are fundamental questions in computer science, and this course attempts to answer (some of) them in a mathematical manner, i.e., with a pencil and a piece of paper. Why? Because such results are beautiful and ingenious. Besides, they do apply in practice more generally than any experiment.

Roughly, we shall talk about the following topics during this course:

Introduction, rules of the game, mathematical preliminaries 1 week
Finite automata and regular expressions 2 weeks
Context-free languages 3 weeks
Turing machines 2 weeks
Undecidability 2 weeks
Complexity 3 weeks

This is an advanced course and will be taught as such. My lectures will presume advanced reading of the matter being discussed. The purpose of the lectures will be to review the basic definitions, explain more in depth the finer points, and go deeper into matter based on your requests. I believe that you will be unable to master the matter of the course relying solely on lectures; you actually need to read the textbook. It may also be possible (though I will try to avoid it) that part of the lectures will be incomprehensible without reading in advance the relevant portion of the textbook.

I expect and welcome requests of covering certain matter more in depth or clarify things, either during (for those physically present) or before the lecture.