CSE2001, Winter 2013

CSE2001: Introduction to Theory of Computation
Fall 2013

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 Stedman Lecture Hall E
Office Hours (tentative): Tue 5:30-6:30 pm, Thu 5:30-6:30 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), Bita Banihashemi (email: bita at cse.yorku.ca)

News

The exam is on Saturday, January 11, 2014, 2pm- 5pm, at TC REXALL.
All marks are on ePost. If you submitted by email, your hw may not have been graded but will be over the next 2-3 days.
The final exam has been postponed due to weather conditions and resulting power outages. I do not have a concrete time but the tentative date in Januarry 11. I will update this page BUT this page will likely NOT be accessible at www.cse.yorku.ca/course/2001. Please bookmark the entire URL so that you can get to this page.
HW 5 solns will be published Dec 19th evening. If you have not done so, please submit your assignment by Dec 19th noon.
HW4 can be submitted upto 4 pm, Monday Dec 2.
Test 2 solutions are here (version 1) and here (version 2).
Test 1 solutions are here (version 1) and here (version 2).
Some information about internships is here.
Being a class representative will help both students and me. Consider applying for this position. Details are here.
I encourage you to try out for programming contests. Details are here.

Assignments

Assignment 1 is here (pdf). Solutions to Assignment 1 are here (pdf). Some comments about HW 1 from the grader are here.
Assignment 2 is here (pdf). Solutions to Assignment 2 are here (pdf).
Assignment 3 is here (pdf). Solutions to Assignment 3 are here (pdf).
Assignment 4 is here (pdf). Solutions to Assignment 5 are here (pdf).
Assignment 5 is here (pdf). Solutions to Assignment 5 are here (pdf).

Tutorials

Final exam review session 2 to be held on Thursday, Dec 19, 2013, 2:00PM to 3:30 pm, room : CLH J.
Final exam review session 1 to be held on Thursday, Dec 12, 2013, 2:00PM to 3:30 pm, room : CB 115.
The tenth tutorial will be held on Wednesday, Dec 4, 2013, 7:30PM to 9 pm, in CLH 110.
The ninth tutorial will be held on Wednesday, Nov 27, 2013, 7:30PM to 9 pm, in LSB (Life Sciences Bldg) 105. We looked at these problems.
The eighth tutorial will be held on Wednesday, Nov 13, 2013, 7:30PM to 9 pm, in LSB (Life Sciences Bldg) 105.
The seventh tutorial will be held on Wednesday, Oct 23, 2013, 7:30PM to 9 pm, in CLH 110.
The sixth tutorial will be held on Wednesday, Oct 16, 2013, 7:30PM to 9 pm, in CB 115.
The fifth tutorial will be held on Wednesday, Oct 9, 2013, 7:30PM to 9 pm, in CLH 110.
The fourth tutorial will be held on Wednesday, Oct 2, 2013, 7:30PM to 9 pm, in CB 115.
The third tutorial will be held on Wednesday, Sep 25 2013, 7:30PM to 9 pm, in CB 115. We looked at these problems.
The second tutorial will be held on Wednesday, Sep 18 2013, 4:00PM to 5:30PM, in TEL 1004. The problems covered, along with some solutions, are here.
The first tutorial will be held on Wednesday, Sep 11 2013, 4:00PM to 5:00PM, in HNE B15.

Lectures

Lec 23 (Dec 3): Ch 4.2: Undecidability. Ch 5.1 (upto pg 220 only) Some undecidable problems. No new slides.
Lec 21 (Nov 28): Ch 4.2: Undecidability. My slides are here(pdf).
Lec 20 (Nov 26): Finished Ch 4.1: Decidability. Start Ch 4.2: Undecidability. My slides are here(pdf).
Lec 19 (Nov 21): Ch 4: Decidability. My slides are here(pdf).
Lec 18 (Nov 14): Ch 3: Turing Machines. No new slides.
Lec 17 (Nov 12): Ch 3: Turing Machines. No new slides.
Lec 16 (Nov 7): Ch 3: Turing Machines. The Church-Turing thesis. My slides are here(pdf).
Lec 15 (Nov 5): Finish Ch 2.3: Non-context-free languages. No new slides.
Lec 14 (Oct 29): Finish Ch 2.2: Pushdown Automata. No new slides. Time permissting, start Ch 2.3: Non-context-free languages. My slides are here(pdf).
Lec 13 (Oct 24): Ch 2.2: Pushdown Automata. No new slides.
Lec 12 (Oct 22): Ch 2: Context-free languages - continued. If time permits, we will start 2.2: Pushdown Automata. My slides are here(pdf).
Oct 17: Test 1, no lecture.
Lec 11 (Oct 15): Ch 2: Context-free languages - continued. No new slides.
Lec 10 (Oct 10): Finish Ch 1.4: Non Regular Languages. Start Ch 2: Context-free languages. My slides are here(pdf).
Lec 9 (Oct 8): Ch 1: Non Regular Languages. My slides are here(pdf). This is Ch 1.4 in the text.
Lec 8 (Oct 3): Ch 1: Regular expressions, equivalence of RL, RE. My slides are here(pdf). This is Ch 1.3 in the text.
Lec 7 (Oct 1): Ch 1: Finite Automata - equivalence of NFA, DFA. My slides are here(pdf). This is Ch 1.2 in the text.
Lec 6 (Sep 26): Ch 1: Finite Automata - nondeterminism. Same slides as before, and these(pdf) new slides. This is Ch 1.2 in the text.
Lec 5 (Sep 24): Ch 1: Finite Automata - continued. Same slides as before, and these(pdf) new slides.
Lec 4 (Sep 19): Start Ch 1: Finite Automata. My slides are here(pdf).
Lec 3 (Sep 17): Finished Mathematical preliminaries. Ch 0 in Sipser - note that we did some extra topics like recursive definitions that are not done well in Sipser. No new slides.
The link to the TIP page as announced in class is here.
Lec 2 (Sep 12): Mathematical preliminaries. Ch 0 in Sipser - continued. No new slides.
Lec 1 (Sep 10): 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

Introduction to the Theory of Computation, Third Edition

website

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.

Grades

Grades can be checked online on ePost here (you need your CSE login/passwd to access it).

4 or 5 assignments, 20% total.
Test 1 (20%): Oct 17, in class, syllabus : Ch 0, 1.1, 1.2, 1.3. Everything covered in class from these sections is included.
An earlier solved midterm is here.
Test 2 (20%) Nov 19, in class. Syllabus: Sections 1.4, 2.1, 2.2, 2.3 plus the definition of regular languages. An old test is here.
Final Exam (40%): scheduled by the registrar: TBA,
Syllabus: Everything covered in the course. A final exam from a previous term is here.

Important dates

Fall classes start: Sept 9
Last date to drop course without receiving a grade : Nov 8.
No Classes: Thanksgiving (Oct 14), Co-curricular days (Oct 30-Nov 3), Study Day (Dec 3)
Classes end: Dec 6
Exam period: Dec 10 - 23 (both inclusive).

Missed test/exam

If you miss a test or 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.

CSE2001: Introduction to Theory of ComputationFall 2013