Computer Science COMP 330A
THEORY OF COMPUTATION

Fall 2012 , Schedule: T-H 10:00-11:30 ENGMD 276

EXAMs are OPEN BOOK -- ALL DOCUMENTATION PERMITTED

OLD FINAL: 2011 (Prof. Panangaden)

Instructor: Prof. Claude Crépeau
Office Hours: Thursday 12h30-15h30 McConnell Eng. Bldg. room 110N

FOR ALL CLASS MATTERS, PLEASE CONTACT cs330@cs.mcgill.ca

T.A.s:
James Hirst
Simon-Keita Brisson
Hang Ma

T.A.'s Office Hours:
James: Tu 13:00-14:30 ENGTR 3110
Simon-Keita: M 10:30-12:00 ENGMC 234
Hang: W 10:30-12:00 ENGTR 3110


---

L E C T U R E S

Lecture 1. Course Outline, and Introduction. Please read subsections 0.2, 0.3 and 0.4 from Textbook. Lecture 2. Regular languages and DFAs. (Textbook section 1.1) Lecture 3. NFAs. (book section 1.2) Lecture 4. NFA-DFA's equivalence + Kleene's theorem. (Textbook section 1.2) Homework 1, due October 2nd 2012 (Hang Ma is TA in charge) Lecture 5. Regular Expressions and Regular Languages. (Textbook section 1.3) Lectures 6-7. NON-Regulat Languages and the Pumping Lemma (Textbook section 1.4) Lecture 8. Myhill-Nerode Theorem and applications (Problems 1.51-1.52) Homework 1, due TODAY (Hang Ma is TA in charge) Homework 2, due October 16, 2012 (James Hirst is TA in charge) Lecture 9. Context-Free Grammars and Languages (Textbook section 2.1) Lecture 10. Pushdown Automata (Textbook section 2.2) Lecture 11. Equivalence between PDA and CFG (Textbook section 2.2) Lecture 12. NON-CFLs and CFG Pumping Lemma (Textbook section 2.3) Homework 2, due TODAY ! (James Hirst is TA in charge)

Lecture 13. (Oct 18, 2012) In class MID-TERM EXAM Lecture 14-15. Turing Machines and CHurch-Turing Thesis (Textbook section 3.1-2-3) Homework 3, due November 13, 2012 (Simon-Keita Brisson is TA in charge) Lecture 16. (UN)Decidability (Textbook sections 4.1-2) Lectures 17-18-19. Reducibility (Textbook Chapter 5) Lecture 20. Intro to complexity (Textbook Chapter 7) Homework 3, due TODAY, (Simon-Keita Brisson is TA in charge) Lecture 21. Recursion Theorem (Prof Panangaden) Lectures 22-23. Intro to complexity / NP-completeness (Textbook Chapter 7) Homework 4, due December 4 , 2012 (Hang Ma is TA in charge) Lecture 24. Probabilistic complexity / Cryptography Lecture 25. Quantum complexity / Cryptanalysis... Lecture 26. REVIEW OF COURSE MATERIAL Homework 4, due TODAY , 2012 (Hang Ma is TA in charge)

---

Required Textbook:

Mike Sipser, MIT

Theory of Computation 3rd Edition, Cengage Learning Editor

Errata to 3rd Edition already exists...

28/11/12