EECS 2001 A: Introduction to Theory of Computation
Summer 2020
General Information
Instructor: Suprakash Datta
Office: LAS, room 3043 (inaccessible until the university opens)
Telephone: (416) 736-2100 ext. 77875 (inaccessible until the university opens)
Lectures: Tue, Thu: 4-5:30 pm online (link on moodle page)
Tutorial: Fri 4-5:30 pm online
Office Hours (tentative): Tue, Thu 5:30-6:30 pm online, or by appointment
Email: [lastname]@eecs.yorku.ca
TA: TBA
News
- Welcome to EECS 2001 A. This public webpage and the course moodle page will together have all the course information.
- Policies about online proctoring will be available before May 20
- There will be a short, 30 min quiz on math background, at 4 pm on May 15 (the scheduled tutorial hour) that you should not study for. This is
meant to check background preparation. This is a CLOSED book and notes quiz. If you do badly in this quiz, you will be given resources and a
chance to retake it (in a couple of weeks).
- I am going to run some job interview practice sessions. Go to
this page, navigate to June 3 and
click on the event on that day.
Lectures
- Lec 1 (May 12): Introduction, Administrivia. My slides are
here (UPDATED).
There is an overview article (for reading at your leisure, relevant but not directly related to this course), here.
- Lec 2 (May 19): Math and logic preview. My slides are
here.
Survey of proof techniques. My slides are
here.
- Lec 3 (May 26): Languages and Problems. My slides are
here.
Introduction to Finite Automata. My slides are
here.
- Lec 4 (June 2) Regular Languages, Non-determinism. My slides are
here (updated).
Properties of regular languages. My slides are
here.
- Lec 5 (June 9) Regular expressions. My slides are
here.
Non-regular languages. My slides are
here.
- Lec 6 (June 16) Context-free languages. My slides are
here.
Chomsky Normal Form. My slides are
here.
Pushdown Automata and closure properties of CFL's. My slides are
here.
- Lec 7 (June 30) Equivalence of CFG, PDA, and non-CFL's. My slides are
here.
Introduction to Turing machines. My slides are
here.
- Lec 8 (July 7) More on Turing machines. My slides are
here.
- Lec 9 (July 14) Decidability (same slides as before).
Introduction to Undecidability - Infinite sets. My slides are
here.
- Lec 10 (July 21) More on Infinite sets (same slides as before).
More on Undecidability. My slides are
here.
- Lec 11 (July 28) More on Undecidability. My slides are
here.
Resources
Textbook
Michael Sipser. Introduction to the Theory of Computation, Third Edition. Cengage Learning, 2013.
Other References
-
Anil Maheshwari and Michiel Smid, Introduction to Theory of Computation, can be downloaded for free here.
- Ding-Zhu Du and Ker-I Ko. Problem Solving in Automata, Languages, and
Complexity. Wiley, 2001.
- John C. Martin. Introduction to Languages and the Theory of
Computation. McGraw-Hill, 2003.
- Daniel Solow. How to Read and Do Proofs: An Introduction to
Mathematical Thought Processes. Wiley, 2002.
- A freely downloadable book on the foundations of Computer Science is
here.
- A freely downloadable book on Discrete Math is here.
Academic Honesty
It is important that you look at the departmental guidelines on
academic honesty.
Although you may discuss the general approach to solving a problem with other people, you should not discuss the solution in detail. You must not take any written notes away from such a discussion. Also, you must list on the cover page of your solutions any people with whom you have discussed the problems. The solutions you hand in should be your own work. While writing them, you may look at the course textbook and your own lecture notes but no other outside sources.
Marking Scheme
| Assignments |
10% |
| Test 1 |
25% |
| Test 2 |
25% |
| Exam |
40% |
Course Learning Outcomes
Upon successful completion of the course a student will be able to:
- Design machines (i.e., finite automata, Turing machines) to solve
specified decision problems.
- Design regular expressions and context-free grammars for a given
language.
- Explain why an object designed in bullets (1) or (2) correctly meets
its specification.
- Prove simple properties about models of computation (e.g., that the
class of regular languages is closed under complement).
- Demonstrate limits of computing by proving that a problem is not
solvable within a particular model of computation.
- Show how one problem can be reduced to another.
Important dates
- Summer classes start: May 11
- Last date to drop course without receiving a grade : July 17
- No Classes: Reading Week (June 23 - 26)
- Classes end: August 12
- Exam period: August 14-21 (both inclusive).
- Test 1: June 12, syllabus : On moodle
- Test 2: July 10 (moved from July 3), syllabus: On moodle
- Final: scheduled by the registrar
Syllabus: Everything covered in the course.