Fall 2013

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 (

TA: Paria Mehrani (email: paria at cse.yorku.ca), Bita Banihashemi (email: bita at cse.yorku.ca)

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

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

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

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

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

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