EECS 2001 N: Introduction to the Theory of Computation
Winter 2025
General Information
Instructor: Suprakash Datta
Office: LAS, room 3043
Lectures: Mon, Wed: 1-2:30 pm in LSB 106
Tutorial: Thu 10-11:30 am in SLH F
Office Hours (tentative): Mon, Wed 5:00-6:00 pm LAS 3043, or by appointment
Email: [lastname]@yorku.ca
TA: TBA
News
- Welcome to EECS 2001 N. This public webpage and the course eClass page will together have all the course information.
Lectures
- Lec 1 (Jan 6): Introduction, Administrivia.
Math and logic preview.
Slides and videos are available on eClass.
There is an overview article (for reading at your leisure, relevant but not directly related to this course), here.
- Lec 2 (Jan 8):
Survey of proof techniques.
Slides and videos are available on eClass.
- Lec 3 (Jan 13): Finite Automata, designing DFAs
- Lec 4 (Jan 15): Designing DFAs continued.
Resources
Textbook
Michael Sipser. Introduction to the Theory of Computation, Third Edition. Cengage Learning, 2013. Publisher site.
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.
Assessment Components
The lower scoring midterm test is worth 15% for each student so the 2 tests are together worth 35%.
| Assignments |
10% |
| Tutorials |
15% |
| Test 1 |
20% |
| Test 2 |
20% |
| 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
- Winter classes start: Jan 6
- No Classes: Reading Week (Feb 15 - 21)
- Last date to drop course without receiving a grade : March 14
- Classes end: April 4
- Exam period: April 8 - 25 (both inclusive)
- Holiday: April 18 (Good Friday)
- Test 1: Feb 10, syllabus : On eClass
- Test 2: Mar 17, syllabus: On eClass
- Final: scheduled by the registrar, syllabus: Everything covered in the course.