Winter 2013

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 (

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

- 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.

- 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.

- 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.

- 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.

- 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% |

- 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.