Fall 2012

Office: CSEB, room 3043

Telephone: (416) 736-2100 ext. 77875

Facsimile: (416) 736-5872

Lectures: Tue-Thu, 4-5:30 pm in Curtis Lecture Hall J

Office Hours (tentative): Tue 5:30-7 pm, Wed 4-6 pm or by appointment

Email: [lastname]@cse.yorku.ca (

TA: Paria Mehrani, email: paria at cse.yorku.ca

- All grades are online.
- The ePost files have been updated to reflect the current grades. Please go through your grades, particularly if they have changed due to reappraisals, to make sure that they are correct.
- Assignment 4 solutions are published.
- An old final is here. Please note that this is only to give you a rough idea and your final may not be identical in format or length.
- Midterm 2 marks are on ePost. The average was 12.5/20, the maximum score was 20/20, the minimum score was 4/20. Solutions are linked at the bottom of this page.
- Solutions to Assignment 3 are published.

- Assignment 1, published on Sep 11, is here (pdf) . Solutions are here (pdf) . Grading instructions for the TA are here (txt) .
- Assignment 2, published on Sep 28, is here (pdf) . Solutions are here (pdf) .
- Assignment 3, published on Nov 06, is here (pdf) . Assignment 3 may be submitted no later than 3:45 pm Nov 27 without penalities. I would still prefer that you submit on time or as early as possible after that. Solutions are here (pdf) .
- Assignment 4, published on Nov 21, is here (pdf) . Solutions are here (pdf) .

- Tutorial 9 (Tue, Dec 4): VH 3009, 3 - 5 pm. We covered these problems.
- Tutorial 8 (Thu, Nov 29), in CLH J, 2:30pm: We will cover these problems on Turing Machines.
- Tutorial 7 (Wed, Nov 14), in ACE 004, 7 pm: We will cover these problems.
- Tutorial 6 (Wed, Nov 7), in ACE 004, 7 pm: We will cover these problems.
- Tutorial 5 (Thurs, Oct 25), in class, 2:30 pm: We will cover these problems.
- Tutorial 4 (Tue, Oct 9), in class, 2:30 pm: We did these problems.
- Tutorial 3 (Wed, Oct 3), Ross N203, 7:00 pm: The problems to be covered are here.
- Tutorial 2 (Wed, Sep 26), Ross N203, 7:00 pm: We did problems 10,11,13 from tutorial 1 and these problems.
- Tutorial 1 (Thu, Sep 20), CLH J, 2:30 pm: We did problems 1-5, 8 from here.

- Lec 21 (Nov 29): Ch 4.2: Undecidability continued. Reductions. My slides are here (pdf).
- Lec 20 (Nov 27): Ch 4.2: Undecidability continued. The Halting Problem, reductions. My slides are here (pdf).
- Lec 19 (Nov 22): Ch 4.2: Undecidability. Prof. Eric Ruppert will teach this class.
- Lec 18 (Nov 20): Start Ch 4: Decidability. My slides are here (pdf).
- Midterm 2 (Nov 15): In class.
- Lec 18 (Nov 13): Complete Ch 3. No new slides.
- Lec 17 (Nov 8): Continue Turing Machines (Ch 3). My slides are here (pdf).
- Lec 16 (Nov 6): Start Turing Machines (Ch 3). My slides are here (pdf).
- Lec 15 (Oct 30): Discuss exam solutions and Mathematical Induction. My slides are here (pdf).
- Lec 14 (Oct 25): Finish Pushdown Automata (same slides as before). Midterm 1 and hw2 handed back.
- Lec 13 (Oct 23): We proved the equivalence of Pushdown Automata and Context-free Languages (no new slides).
- Lec 12 (Oct 18): Continue Pushdown Automata (same slides as before). Start non-context-free languages: my slides are here (pdf).
- Oct 16: First midterm test. No lecture.
- Lec 11 (Oct 11): We will continue Context Free Languages (Ch 2). We will finish the previous set of slides and may start Pushdown Automata; my slides are here (pdf).
- Lec 10 (Oct 9): We will start Context Free Languages (Ch 2). My slides are here (pdf).
- Lec 9 (Oct 4): We will complete the coverage of non-regular languages. We will prove the Pumping Lemma and look at several examples of its use in proving languages non-regular.
- Lec 8 (Oct 2): We will complete the equivalence of RE, RL (old slides). We will then cover non-regular languages. My slides are here (pdf).
- Lec 7 (Sep 27): We will prove the equivalence of DFA, NFA (old slides). We will then cover regular expressions. My slides are here (pdf).
- Lec 6 (Sep 25): We will cover examples of nondeterministic finite automata, and also closure under regular operations. The same slides as before. We will then prove the equivalence of DFA and NFA and introduce regular expressions. My slides are here (pdf).
- Lec 5 (Sep 20): We will highlight problems designing DFA and introduce non-determinism and nondeterministic finite automata. My slides are here (pdf).
- Lec 4 (Sep 18): Several examples will be worked out in class. The same slides as the last class.
- Lec 3 (Sep 13): Review of proof techniques.
We will use the same slides as before and these extra slides (pdf).

Introduction to automata. My slides are here (pdf).

Some notes on the lecture are here.

- Lec 2 (Sep 11): Mathematical preliminaries continued. Very brief logic review. Functions, strings, languages. The relationship between function computation and language acceptance.
The same set of slides as the previous class.
Some notes on the lecture are here.

- We are again looking for students to participate in the ACM programming contests at York. This is a great chance to possibly represent your University. To get more information about eligibility, format, time etc please visit our contest page.
- Lec 1 (Sep 6): Mathematical preliminaries.
My slides are here (pdf).

Some notes on the lecture are here.

Click here for some humor regarding proof techniques. - Welcome to CSE 2001

- Michael Sipser.

- 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 has some online notes that he uses when he teaches this course.
- A freely downloadable book on the foundations of Computer Science is here.
- A freely downloadable book on Discrete Math is here.

4 assignments, weighted equally | 20% |

Test 1 | 20% |

Test 2 | 20% |

Exam | 40% |

- Fall classes start: Sept 5
- Last date to drop course without receiving a grade : Nov 9
- No Classes: Thanksgiving (Oct 8), Co-Curricular Days (Oct. 31-Nov. 4)
- Classes end: Dec 3.
- Exam period: Dec 5- 21 (both inclusive).
- Midterm 1: Oct 16, in class. The syllabus is Ch 0, Ch 1.1, 1.2, 1.3.
An old test is here. Please note that the syllabus was different and so some of the questions are not relevant for this midterm.

The solutions to the midterm are version 1 , and version 2 . Please note that Q1,2 are not solved in version 2. These solutions will be added later. - Midterm 2: Nov 15, in class. Syllabus: Ch 1.4, 2.1, 2,2, 2,3
An old test is here. Please note that the syllabus was different and so some of the questions are not relevant for this test.

The solutions to the midterm are version 1 , and version 2 . - Final: Scheduled by the registrar, Thu, 6 Dec 2012, 9:00 am - 12 noon, room ACW 206.

Syllabus: Everything covered in the course.