CSE2001: Introduction to Theory of Computation Fall 2012
General Information
Instructor: Suprakash Datta 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 (While you are free to send me email from any account,
please realize that email from domains other than yorku.ca have a higher chance
of entering my spam folder. I do check my spam folder irregularly , but to be
safe, consider using your cs account when sending me email.)
TA: Paria Mehrani, email: paria at cse.yorku.ca
News
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.
Grades
Grades can be checked online on ePost here (you need your CSE login/passwd to access it).
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) .
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.
Lectures
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
Resources
Textbook
Michael Sipser. Introduction to the Theory of Computation, Third
Edition. website. Cengage Learning, 2013.
If you have the second edition, here is the Errata.
Other 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 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.
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
4 assignments, weighted equally
20%
Test 1
20%
Test 2
20%
Exam
40%
Important dates
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.