CSE 2001
Introduction to Theory of Computation
Summer 2013

Course Description

The course introduces different theoretical models of computers and studies their capabilities and theoretical limitations. Topics covered typically include the following.

• Finite automata and regular expressions; practical applications, e.g., text editors.
• Pushdown automata and context-free grammars; practical applications, e.g., parsing and compilers.
• Turing machines as a general model of computers; introduction to unsolvability: the halting problem.

What's New

• August 23: Grades have been submitted. The class average is 65.4%. You can pick assignment 4 and other remaining assignments and tests; they are in a box outside LAS 3052. You can have a look at your final exam on Sept 24 and Sept 26 at 1pm in LAS 3052A. The instuctor is away until Sept 24, but can be contacted by email.
• August 8: Solutions to assignment 3 are here.
16:00 to 18:00 in LAS 2052, where the TA Wendy Ashlock will answer your questions. The instructor is away at a conference until August 12 and he will not have office hours on Aug. 5 and Aug. 8; but he can be contacted by email.
• Here is a final exam from a previous term.
• The final exam is on Monday August 12 09:00-12:30 in CLH K. It covers everthing we have seen this term (including the material discussed at the rescheduled class on July 26). There will be more emphasis on the material we have seen since the second test (i.e. Sipser Chapters 3, 4, and 5), but there will also be questions on the earlier material.
• July 30: The ninth tutorial will be on Wed. July 31 17:00-18:30 in LAS 3033. The office hour will be held just before the tutorial from 16:00 to 17:00 in LAS 3052 and there will be no office hour on Thursday August 1.
• July 27: Assignment 4 is out; officially it due on August 2 by 17:00 in the dropbox; but it can be submitted without penalty until August 7 at 17:00 in the dropbox.
• July 23: The deadline for Assignment 3 has been extended; it is now due on July 26 at 17:00 in class or in the dropbox. Also note that there is no tutorial this week and that the office hours are at the usual time i.e. on July 25 and 29 17:00-18:00 in LAS 3052.
• July 16: There will be a make up lecture on Friday July 26 17:00-20:00 in CLH J to compensate for the July 8 class that had to be cancelled due to the storm and power outage.
• July 16: This week's office hour will be on Wed. July 17 16:00-17:00 (in LAS 3052) instead of the usual Thu. 17:00-18:00 time.
• July 15: Assignment 3 is out; it due on July 26 by 17:00 in class or in the dropbox (extended!).
• The eight tutorial will be on Wed. July 17 17:00-18:30 in LAS 3033.
• Solutions to assignment 2 are here.
• A reminder that the second test will be on July 15 19:00 to 20:20. It will cover everything we have seen up to and including Week 8, i.e. Sipser Ch. 0, 1, and 2, excluding Section 2.4. The focus will be on Sections 1.4, 2.1, 2.2, and 2.3.
• July 9: Due the storm and power outage, the July 8 class was cancelled. There is a 24h extension for handing in Assignment 2; please submit it in the drop box by 19:00 on July 9.
• The seventh tutorial will be on Wed. July 10 17:00-18:30 in LAS 3033.
• The sixth tutorial will be on Wed. July 3 17:00-18:30 in LAS 3033.
• June 24: Assignment 2 is out; it due on July 8 by 18:45 in the dropbox, or 19:00 in class (extended to July 9 at 19:00).
• The second test will be on July 15 19:00 to 20:20. Details on the material covered will be announced later.
• The fifth tutorial will be on Wed. June 26 17:00-18:30 in LAS 3033.
• The fourth tutorial will be on Wed. June 19 17:00-18:30 in LAS 3033.
• June 11: There in no tutorial this week.
• Solutions to assignment 1 are here.
• The instructor office hour on Thu. June 6 is moved to 16:00-17:00 in LAS 3052A so to avoid conflict with the third tutorial.
• The third tutorial will be on Thu. June 6 17:00-18:30 in Ross South 203.
• The first test will be on June 10 19:00 to 20:20. It will cover the material in Sipser Ch. 0 and Ch. 1 Sections 1, 2, and 3. Here is a sample first test from a previous term with solutions.
• The second tutorial will be on Wed. May 29 17:00-18:30 in LAS 3033.
• May 20: Assignment 1 is out; it due on June 3 by 18:45 in the dropbox, or 19:00 in class.
• May 14: The office hour this week will be on Thursday May 16 16:00-17:00 in LAS 3052 and the TA Paria Mehrani will be there to answer questions. On May 20 the university is closed and there is no class. The first tutorial, led by Paria, will be on Wednesday May 22 17:00-18:30 in LAS 3033; there will also be an office hour there after the tutorial. The instructor office hour on May 23 is cancelled.
• May 9: Readings, suggested exercises, and lecture notes for week 1 have been posted below.
• Classes start May 6.

Instructor

Prof. Yves Lespérance
Office: LAS 3052A
Tel: 736-2100 ext. 70146
Email: lesperan "at" cse.yorku.ca

Lectures

Monday 19:00 to 22:00 in CLH K (CLH is Curtis Lecture Halls).

Instructor Office Hours

Monday and Thursday from 17:00 to 18:00 in LAS 3052A.

Textbook

Michael Sipser, Introduction to the Theory of Computation, Third Edition Cengage Learning, 2013. Book web site.

If you have the second edition, here is the errata.

The textbook is required; it is available at the York University Bookstore.

Prerequisites

General prerequisites; CSE1019 3.00.

Evaluation Scheme

Assignements (4 @ 5% each)	20%
Tests (2 @ 20% each)	40%
Final exam	40%
Total	100%

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.

Readings, Suggested Exercises, and Lecture Transparencies

• Week 1 (May 6) Introduction & Mathematical Foundations
  Required Readings: Sipser Chapter 0.
  Suggested Exercises: Sipser 0.1 to 0.12.
  Lecture transparencies.
• Week 2 (May 13) Finite Automata
  Required Readings: Sipser Section 1.1.
  Suggested Exercises: Sipser 1.1-1.6, 1.27, 1.31-1.34, 1.48.
  Lecture transparencies.
• Week 3 (May 20) Victoria Day holiday, no lecture, but there is a tutorial (see What's New above).
• Week 4 (May 27) Finite Automata and Regular Languages
  Required Readings: Sipser Sections 1.2 to 1.4 inclusive.
  Suggested Exercises: Sipser 1.7-1.11 (a few parts of each), 1.12, 1.13-1.16, 1.17-1.23, 1.28(b), 1.36, 1.38, 1.39, 1.40, 1.42, 1.44.
  Lecture transparencies (updated!).
• Week 5 (June 3) The Pumping Lemma and Non-Regular Languages
  Required Readings: Sipser Section 1.4.
  Suggested Exercises: Sipser 1.29, 1.30, 1.46, 1.47, 1.49, 1.54, 1.55(a-b), 1.58
  Lecture transparencies.
• Week 6 (June 10) Context-Free Languages
  Required Readings: Sipser Sections 2.1 and 2.2.
  Suggested Exercises: Sipser 2.1, 2.3, 2.4, 2.6, 2.8, 2.9, 2.15, 2.16, 2.25, 2.5, 2.7, 2.10
  Lecture transparencies.
• Week 7 (June 17) Context-Free Languages and Pushdown Automata
  Required Readings: Sipser Sections 2.2 and 2.3.
  Lecture transparencies.
• Week 8 (June 24) Non-Context-Free Languages and CFL Pumping Lemma
  Required Readings: Sipser Section 2.3.
  Suggested Exercises: Sipser 2.2, 2.13, 2.30, 2.31, 2.32, 2.35.
  Lecture transparencies (updated!).
• Week 9 (July 15) Turing Machines and the Church-Turing Thesis
  Required Readings: Sipser Chapter 3.
  Suggested Exercises: Sipser 3.1(b), 3.2(a,e), 3.5, 3.7, 3.8(a), 3.10, 3.12, 3.13, 3.15, 3.16, 3.22.
  Lecture transparencies (updated!).
• Week 10 (July 22 & July 26) Decidability
  Required Readings: Sipser Chapter 4.
  Suggested Exercises: Sipser 4.5, 4.6, 4.7
  Lecture transparencies part 1 , part 2 .
• Week 11 (July 29) Reducibility
  Required Readings: Sipser Chapter 5 Section 1 pages 215 to 220 as well as all of Section 3.
  Suggested Exercises: Sipser 5.12, 5.13, 5.4-5.7, 5.9-5.11, 5.22, 5.23
  Lecture transparencies (updated!).

Additional References

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.

Jeff Edmonds, Abstract Thinking, Intro to the Theory of Computation: SC/COSC 2001 3.0 Lecture Notes, Winter 99-00 Version 0.2, available here.