EECS 2001 N: Introduction to Theory of Computation
Winter 2020
General Information
Instructor: Suprakash Datta
Office:
CSEB, room 3043
Telephone: (416) 736-2100 ext. 77875
Lectures: Mon-Wed, 2:30-4 pm in LAS B
Tutorial: Fri 2:30-4 pm in LAS B
Office Hours (tentative): Mon, Wed 4-5 pm, or by appointment
Email: [lastname]@eecs.yorku.ca
TA: Yunge Hao, Irfa Nisar
News
- Welcome to EECS 2001 N. This public webpage and the course moodle page will together have all the course information.
Assignments
- Assignment 1
- Assignment 2 is
here.
- Assignment 3 is on moodle.
- Assignment 4 is on moodle.
Tutorials
- The first tutorial will be held on Friday, Jan 10 2020, 2:30PM to 4:30PM in LAS B.
The problems are
here.
- The Second tutorial will be held on Friday, Jan 17 2020, 2:30PM to 4:30PM in LAS B.
The problems are
here. Solutions are on Moodle.
Lectures
- Lec 1 (Jan 6): Introduction, Administrivia. My slides are
here.
There is an overview article (for reading at your leisure, relevant but not directly related to this course), here.
- Lec 2 (Jan 8):
Mathematical preliminaries. My slides are
here.
Some terminology. My slides are
here.
We covered slides 1-3 in this set.
Relevant sections: Ch 1.1, 1.2.
- Lec 3 (Jan 13): Finish Mathematical preliminaries (the last set of slides). Start Finite Automata.
My slides are
here.
- Lec 4 (Jan 15): Finish the last set of slides. More on Finite Automata. My slides are
here.
We reached slide 11.
- Lec 5 (Jan 20): Finish the last set of slides. More on Finite Automata. My slides are
here.
- Lec 6 (Jan 22): More on Finite Automata.
- Lec 7 (Jan 31): More on Finite Automata. Examples of NFA to DFA conversion, regular expressions
- Lec 8 (Feb 3): Non-regular Languages. My slides are
here.
- Lec 9 (Feb 5): Regular and Context free grammars. My slides are
here.
- Lec 10 (Feb 10): More on Context free grammars. My slides are
here.
- Lec 11 (Feb 12): More on Context free grammars. My slides are
here.
- Lec 12 (Feb 24): More on Context free grammars. My slides are
here.
- Lec 13 (Feb 26): More on Context free grammars.
- Lec 14 (Mar 2): Intro to Turing Machines (no slides used).
- Lec 15 (Mar 9): Intro to Turing Machines. My slides are
here.
- Lec 16 (Mar 11): More on Turing Machines. My slides are
here.
- Lec 17 (Mar 16): More on Turing Machines. Universal TM, Decidability. My slides are
here.
This lecture, and all subsequent ones, are fully on video. Please watch at your convenience.
- Lec 18 (Mar 18): More on Decidable Languages. My slides are
here.
Building tools for proving undecidability. My slides are
here.
- Lec 19 (Mar 23): Proving undecidability - diagonalization arguments. My slides are
here.
- Lec 20 (Mar 25): Proving specific languages to be undecidabile or unrecognizable. My slides are
here.
- Lec 21 (Mar 30): More on proving specific languages to be undecidabile or unrecognizable. My slides are
here.
- Lec 22 (Apr 1): More on proving specific languages to be co-unrecognozable or unrecognizable. My slides are
here.
(Updated 10 am on Apr 1)
Resources
Textbook
Anil Maheshwari and Michiel Smid, Introduction to Theory of Computation, can be downloaded for free here.
Other References
- Michael Sipser. Introduction to the Theory of Computation, Third Edition. website. Cengage Learning, 2013.
- 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 HonestyIt 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
| 4 assignments |
15% |
| Test 1 |
15% |
| Test 2 |
20% |
| Exam |
50% |
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
- Winter classes start: Jan 6
- Last date to drop course without receiving a grade : Mar 15.
- No Classes: Reading Week (Feb. 15-21), Good Friday (Apr 10).
- Classes end: April 5
- Exam period: April 7 - 25 (both inclusive).
- Midterm 1: Jan 29. in-class, syllabus : TBA
- Midterm 2: March 4, in class. Syllabus: TBA
- Final: scheduled by the registrar
Syllabus: Everything covered in the course.