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: Guodong Li | Office Hours: Wed. 3--5 (MEB 3157) |
The first class is on August 21. The last class will be held December 6. Days on which class will not be held include
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 |
|---|---|---|---|
| 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 Pumping lemma | Finite State Automata
Non-deterministic FSAs Regular expressions Equivalences Pumping lemma Minimization |
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 Lecture 21 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:
| 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.
Exam 2 will cover all aspects of what we learn about context-free languages and grammars. It will be held November 15, in class. A collection of questions from old tests.
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. A couple of old tests.