This course provides an introduction to some aspects of theoretical computer science. The topics covered provide an abstract and mathematical treatment of computation. This approach enables one to precisely state and prove general and far-reaching facts about computational models such as finite state automata, context-free grammars, and Turing machines.
The course involves no programming; you can think of it as a mathematics class where the object of study is computation. (In spite of that, it can be a lot of fun.) Taking this course will give you fundamentals necessary to more advanced Computer Science courses. It will also develop your problem-solving capabilities, since we will tackle many problems.
| Instructor Konrad Slind (MEB 3436) | Office Hours: Tuesday after class, or by appointment |
| Class Time Tu/Thu, 12:25-1:45 | Class Room WEB 2230 |
| TA: Jianjun Duan | Office Hours: Monday, 10-11, MEB 3445 |
| TA: Christoper Earl | Office Hours: Wednesday, 1-2 pm, MEB 3115 |
Noteworthy dates
The University Academic Calendar may be consulted for further information about drop dates and other important dates in the semester.
| Introduction to Rigorous Proof | Computability | Context-Free Languages | Regular Languages | More |
|---|---|---|---|---|
| Basic Set Theory and Logic
Basics of Proof Alphabets, Strings, and Languages | Turing Machines
Register Machines Church-Turing thesis R.E. sets Undecidability | Grammars
Normal Forms Push-down automata Equivalences Parsing | Finite State Automata
Non-deterministic FSAs Regular expressions Equivalences Minimization | Chomsky Hierarchy
Pumping Lemmas Rice's Theorem Automata-like formalisms |
Lecture 1 Lecture 2 Lecture 3 Lecture 4 Lecture 5 Lecture 6 Lecture 7 Lecture 8 Lecture 9 Lecture 10 Lecture 11 Lecture 12 Lecture 13 Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Lecture 19 Lecture 20 Cumulative notesThe material covered in lectures is what you will be tested on, and will be the basis of the assignments. Therefore attendance is important. A lot of students have asked to see the notes a day or two before class; that would be hard for me to achieve regularly. As kind of a compromise, I am offering last year's notes in the hopes that they will help. But of course, if there is a difference between the notes of last year and this year, this year's notes will take precedence.
Here is a sampling of the many excellent books on this topic. They should all be in the library, and some are in the departmental library:
Alan Turing's 1936 paper introduced Turing machines, proving undecidability of the Halting Problem, and discussing computability of functions on the real numbers. Turing led a very interesting life; unfortunately, his tragic death cut short a brilliant career.
JFLAP is a program that can help you construct and experiment with a variety of the formal machines we discuss in this course. Try it out!
Exam 1 will cover Turing machines and computability. It will be held October 2, in class. Here are some tests from previous years.
Exam 2 will cover all aspects of what we learn about context-free languages and grammars. It will be held November 4, in class. Here are some tests from previous years.
Exam 3 will will cover all aspects of what we learn about automata and regular languages: DFAs, NFAs, regular expressions, closure properties, equivalences, minimization, and the pumping lemma. It will be held December 11, in class.
| Assignments | 50% |
| Exams (2 midterms and a final) | 50% |
| Total | 100% |
Assignments will be given every one or two weeks. Assignments will be handed in to me at the beginning of class. If a due assignment is not in my possession by the time class starts, it is deemed to be late. You are allowed a maximum of 2 late submissions. A late submission can be at most 24 hours late: after that it will not be accepted and you will get no marks for the assignment.
Should you discover what you think is an error in grading, you have exactly one week after the grades are posted to request for regrading. You should first go and see the TA who graded your work and see if you can get it resolved. If you are still unsatisfied, then you should go and see Professor Slind.