CSE2001: Introduction to Theory of Computation Winter 2013
General Information
Instructor: Suprakash Datta Office:
CSEB, room 3043 Telephone: (416) 736-2100 ext. 77875
Facsimile: (416)
736-5872
Lectures: Mon-Wed, 2:30-4 pm in Curtis Lecture Hall M
Office Hours (tentative): Mon 4-6 pm, Tue 3-4 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 marks are now on ePost. Final grades are unofficial until approved by the dept.
If you miss the final due to medical reasons you are required to contact the instructor within 7 days of the scheduled exam with documentation. York University has a new form that your doctor should fill out. You can download it by clicking here.
Grades
Grades can be checked online on ePost here (you need your CSE login/passwd to access it).
Assignments
Assignment 1 is here (pdf).
The solutions to Assignment 1 are here.
Assignment 2 is here (pdf). The deadline is postponed to Friday (Mar 8) noon. This is a hard deadline. No assignments are going to be accepted after solutions are published on Friday. Solutions are
here.
Assignment 3 is here (pdf).
Assignment 3 can be handed in without penalty upto 2:15 pm in the dropbox or 2:40 pm in class on Monday, March 25. Solutions to assignment 3 are here.
Assignment 4 is here (pdf).
Solutions to assignment 4 are here.
Tutorials
The first tutorial will be held in R N203 Tuesday, Jan 15 2013, 2:30PM to 4:30PM. The problems we discussed are here(pdf).
The second tutorial will be held in R N203 Tuesday, Jan 22 2013, 2:30PM to 4:30PM. This will be primarily on Induction, and recursive definitions.
The problems we discussed are here(pdf).
The third tutorial will be held in TEL 0005, Tuesday, Jan 29 2013, 2:30PM to 4:00PM. This will be primarily on FA design.
The problems we discussed are here(pdf).
The fourth tutorial will be held in SLH B, Monday, Feb 4 2013, 5:00PM to 6:30PM.
The problems to be discussed are here(pdf).
The fifth tutorial will be held in SC 214 Tuesday, Feb 12 2013, 3:00PM to 4:30PM.
The sixth tutorial will be held in LSB 106, on Thursday Mar 7, from 2:30PM to 4:00PM.
The problems to be discussed are here(pdf).
The last 4 problems could note be solved in the tutorial for lack of time.
Solution sketches are here(pdf).
The seventh tutorial will be held in CLH H, on Thursday Mar 14, from 3:30PM to 5:00PM.
The eighth tutorial will be held in LSB 106 on Wed Mar 20 2013, from 7:00PM to
8:30PM.
The problems to be discussed are here(pdf).
The ninth tutorial will be held in LSB 106 on Wed Mar 27 2013, from 7:00PM to
8:30PM.
The tenth tutorial will be held in R N 203 on Wed Apr 3 2013, from 7:00PM to
8:30PM. The problems to be discussed are here(pdf).
Tutorial 4- 6 pm, Monday April 15, SLH 107. This will be mostly exam review.
Tutorial 5:30- 7 pm, Wednesday April 17, Lassonde (CSEB) 3033, This will be identical to the one on April 15. If you came on April 15, you need not come to this one.
Lectures
Lec 18 (Apr 1): Undecidability continued. My slides are here(pdf).
Lec 18 (Mar 27): Undecidability. My slides are here(pdf).
Lec 17 (Mar 25): Decidability. My slides are here(pdf).
Lec 17 (Mar 20): Variants of Turing Machines. My slides are here(pdf).
Lec 16 (Mar 18): Introduction to Turing Machines - contd. No new slides.
Lec 15 (Mar 13): Introduction to Turing Machines. My slides
are here(pdf).
Lec 14 (Mar 6): Non context-free languages (no new slides). Midterm review.
Lec 13 (Mar 4): Context-free languages continued. If needed, we will use these additional slides (pdf).
Lec 12 (Feb 27): Context-free languages continued. If needed, we will use these additional slides (pdf).
Lec 11 (Feb 25): Context-free languages. My slides
are here(pdf).
Lec 10 (Feb 11): Non-regular languages continued. No new slides.
Lec 9 (Feb 6): Regular expressions contd. Non-regular languages. My slides are here(pdf).
Lec 8 (Feb 4): Nondeterministic Finite Automata -- equivalence with DFA = contd. Regular expressions. My slides are here(pdf).
Lec 7 (Jan 30): Nondeterministic Finite Automata -- equivalence with DFA. My slides are here(pdf).
Lec 6 (Jan 23): Nondeterministic Finite Automata (Ch 1) -- continued. Same slides as before.
Lec 5 (Jan 21):
Introduction to Finite Automata (Ch 1) -- continued. Same slides as before.
Lec 4 (Jan 16): Introdcution to proofs continued. Same slides as before, and these extra slides(pdf). Introduction to Finite Automata (Ch 1) -- my slides are here(pdf).
Lec 3 (Jan 14): Mathematical preliminaries continued. Introdcution to proofs. Same slides as before.
Lec 2 (Jan 9): Mathematical preliminaries continued. Same slides as before.
Lec 1 (Jan 7): Mathematical preliminaries. Ch 0 in Sipser. My slides are
here(pdf).
Welcome to CSE 2001. Click here for some humor regarding proof techniques.
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
Winter classes start: Jan 7
Last date to drop course without receiving a grade : Mar 15.
No Classes: Reading Week (Feb. 16-22), Good Friday (Mar 29).
Classes end: April 8 (Monday, April 8 is a virtual Friday).
Exam period: April 10 - 26 (both inclusive).
Midterm 1: Feb 13, syllabus : Ch 0, Ch 1.1, Ch 1.2 and recursive definitions. An earlier solved midterm is here.
Solutions to the midterm are: version 1
and version 2.
Midterm 2: March 11, in class. Syllabus: regular expressions, non-regular languages, context-free languages and pushdown automata. An old test is
here. As mentioned in class, the test covers Ch 1.3, 1.4, 2.1, 2.2.
Final: scheduled by the registrar:Sat, 20 Apr 2013, 9:00 am - 12 noon, in LAS B,
Syllabus: Everything covered in the course.
A final exam from a previous term is here.