Instructor: Prof. Claude Crépeau

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

T.A.'s and Office Hours:
Claude : Wednesday 13:00-16:00 ENGMC 110N
Pouriya Alikhani : Friday 12:00-14:00 ENGTR 3090
Anirudha Jita : Monday 16:00-17:00 ENGTR 3090
Justin Li : Tuesday 15:00-16:00 ENGTR 3110
Yanjia Li : Friday 10:00-11:00 ENGTR 3110
Shiquan Zhang : Thursday 15:00-16:00 ENGTR 3090








L E C T U R E S (VIDEOs)

Lecture 1. (3 SEP 2019) Course Outline, and Introduction Please read subsections 0.2, 0.3 and 0.4 from Book. (VIDEO) Lecture 2. (5 SEP 2019) Introduction + Regular languages and DFAs (Book section 1.1) (VIDEO) Lecture 3. (10 SEP 2019) Deterministic Finite Automata. (book section 1.1) (VIDEO) Lecture 4. (12 SEP 2019) Regular ops + NFA. (Book sections 1.1-1.2) (VIDEO) Homework 1 OUT, due OCT 1, 2019 (TAs: Pierre-William, Anirudha, Shiquan) Lecture 5. (17 SEP 2019) NFA=DFA. (Book sections 1.2) (VIDEO) Lecture 6. (19 SEP 2019) Myhill-Nerode Theorem and applications (Problems 1.51-1.52) (VIDEO) Lecture 7. (24 SEP 2019) Regular Expressions and Languages. (Book section 1.3) (VIDEO) Lectures 8. (26 SEP 2019) Regular and NON-Regulat Languages (Book section 1.4) (VIDEO) Lectures 9. (1 OCT 2019) the Pumping Lemma (Book section 1.4) (VIDEO) Homework 1 IN, due TODAY (TAs: Pierre-William,Anirudha, Shiquan) Homework 2 OUT, due OCT 15, 2019 (TAs: Pouriya, Justin, Yanjia) Lecture 10. (3 OCT 2019) Context-Free Grammars and Languages, including CNF. (Book section 2.1) (VIDEO) Lecture 11. (8 OCT 2019) Pushdown Automata (Book section 2.2) (VIDEO) Lecture 12. (10 OCT 2019) Equivalence between PDA and CFG (Book section 2.2) (VIDEO)

Lecture 13. (15 OCT 2019) NON-CFLs and CFG Pumping Lemma (Book section 2.3) (VIDEO) Homework 2 IN, due Oct 15 (TAs: Pouriya, Justin, Yanjia) Lecture 14. (OCT 17 2019) MIDTERM review (VIDEO) Lecture 15. (OCT 17 2019) Evening MID-TERM EXAM 18:00-19:30 Lectures 16-17. (OCT 22-24, 2019) Turing Machines and Church-Turing Thesis (Book section 3.1-2-3) (VIDEO 16) (VIDEO 17) Homework 3 OUT, due November 7 , 2019 (TAs: Yanjia, Anirudha, Shiquan) page 1 JPG, page 2 JPG, page 3 JPG, Lectures 18-19. (OCT 29-31, 2019) (UN)Decidability (Book sections 4.1-2) (VIDEO 18) (VIDEO 19) Lectures 20-21. (NOV 05-07, 2019) Reducibility (Book Chapter 5) (VIDEO 20) (VIDEO 21) Homework 3 IN, due November 7 , 2019 (TAs: Yanjia, Anirudha, Shiquan) Homework 4 OUT, due November 28 , 2019 (TAs: Pouriya, Justin, Pouriya) Lectures 22-23. (NOV 12-14, 2019) Intro to complexity / NP-completeness (Book Chapters 7,8.1,8.2,8.3) (VIDEO 22) (VIDEO 23) Lectures 24-26. (NOV 19-26-28, 2019) Probabilistic/Quantum complexity & Cryptography... (VIDEO 24) (VIDEO 25) (VIDEO 26) Homework 4 IN, due November 28 , 2019 (TAs: Pouriya, Justin, Pouriya) Lecture 26B. (TBA, 2019) REVIEW OF COURSE MATERIAL (VIDEO 27) FINAL EXAM. (DEC 19 2019) PRACTICE EXAM FROM 2017 % = = = = = = = = = - - ↑↑↑↑ 2019 ↑↑↑↑ - - = = = = = = = = = % % = = = = = = = = = - - UPDATE LINE - - = = = = = = = = = % % = = = = = = = = = - - ↓↓↓↓ 2017 ↓↓↓↓ - - = = = = = = = = = %

---

Required Textbook:

Mike Sipser, MIT

Theory of Computation 3rd Edition,
Cengage Learning Editor
3rd Edition Table of Contents

Errata to 3rd Edition

30 NOV 19