Winter 2021

- Official lecture times: Monday and Wednesday, 10:05 - 11:25am.
- There won't be live lectures. Instead, links to pre-recorded video lectures will be posted in the section "What was done in class".

- First lecture is on Monday January 11.
- February 15-19: Winter break, no classes.
- Last lecture is on Monday April 12.
- Wednesday April 14: Last day of classes in the winter term. Classes follow a Friday schedule.

- Mohammad Nokhbeh Zaeem: Monday, 2-4pm, on Zoom, click on the name.
- Michiel Smid: Tuesday and Thursday, 4-5pm, on Google Meet, click on the name.
- Yunkai Wang: Wednesday, 2-4pm, on Discord, username: Yunkai#3311

- Assignment 1: posted January 24, due February 7
- Assignment 2: posted February 7, due February 28
- Midterm: Monday March 1, 10:00 - 11:30am
- Assignment 3: posted March 14, due March 28
- Assignment 4: posted March 28, due April 11
- Final exam: TBA

- Assignments: 25%
- Midterm: 25%
- Final exam: 50%

- Late assignments will
**not**be accepted. - Real computer scientists use LaTeX to type their solutions. In case you want to learn LaTeX, here is a tutorial.
- You can use the freely available Ipe drawing editor to make figures.
- Each assignment must be submitted as one single PDF file through cuLearn.
- You can type your solutions, or write them by hand and scan them (for example, using a scan app on your phone or using a real scanner).

- Assignment 1 is due Sunday February 7, before 23:59.

- The midterm will be on Monday March 1, 10:00 - 11:30am.
- Details TBA.

- Details TBA.

- First offence, first-year students (less than 4.0 credits completed): No credit for assessment(s) in question, or a final grade reduction of one full letter grade (e.g., A- becomes B-), whichever is a greater reduction.
- First offence (anyone else): A grade of F in the course.
- Second offence (anyone): A grade of F in the course and a one-term suspension from studies.
- Third offence: Expulsion from the University.

- January 11:
- Video lecture 1, part 1: short introduction.
- Video lecture 1, part 2.
- Overview; Sections 1.1 and 2.1; example on page 23. (Take a quick look at Sections 1.2 and 1.3.)

- January 13:
- Video lecture 2, part 1.
- Video lecture 2, part 2.
- Deterministic finite automata: definition and examples (Section 2.2).

- January 18:
- Union/intersection/complement of regular languages is regular; regular operations: union, concatenation, and star (Section 2.3);
- Video lecture 3.

- January 20:
- Nondeterministic finite automata (Sections 2.4.1, 2.4.2, and 2.4.3), definition of nondeterministic finite automaton (Section 2.4.4).
- Video lecture 4.

- January 25:
- Equivalence of deterministic and nondeterministic finite automata (Section 2.5).
- Video lecture 5.

- January 27:
- Closure under the regular operations (Section 2.6); Exercise 2.18.
- Video lecture 6.

- February 1:
- Regular expressions (Section 2.7); how to convert a regular expression to an NFA (Section 2.8.1).
- Video lecture 7.

- January 31: How to convert a DFA to a regular expression (Section 2.8.2). The Pumping Lemma for regular languages (Section 2.9); some examples from Section 2.9.1.
- February 5: Pumping Lemma: more examples from Section 2.9.1; brief introduction to context-free grammars (Section 3.1).
- February 7: Definition of context-free grammars (Section 3.1); examples of context-free grammars (Section 3.2).
- February 12: Converting a DFA to a CFG, every regular language is context-free (Section 3.3); Chomsky Normal Form; converting a context-free grammar to Chomsky Normal Form (Section 3.4).
- February 14: Deterministic pushdown automata (Sections 3.5, 3.6.1, 3.6.2).
- February 18-22: Winter break.
- February 26: Nondeterministic pushdown automata (Section 3.6.3); converting a context-free grammar to a nondeterministic pushdown automaton (Section 3.7).
- February 28: ???
- March 5: Pumping lemma for context-free languages (Section 3.8); proof of the pumping lemma (Section 3.8.1); first example in Section 3.8.2.
- March 7: Examples of languages that are not context-free (Section 3.8.2).
- March 12: Solutions midterm.
- March 14: Turing machines (Section 4.1); examples of Turing machines (Sections 4.2.1 and 4.2.2).
- March 19: Examples of Turing machines (Sections 4.2.3, 4.2.5); equivalence of multi-tape Turing machines and single-tape Turing machines (Section 4.3).
- March 21: What is an algorithm? Church-Turing Thesis (Section 4.4); Definition of a language being decidable (Section 5.1); the languages A_DFA, A_NFA, and A_CFG are decidable; every context-free language is decidable (Sections 5.1.1, 5.1.2, 5.1.3); the Halting Problem is undecidable (Section 5.1.5).
- March 26: Hilbert's Hotel: countable sets, the real numbers are not countable (Section 5.2); the Halting Problem revisited (Section 5.2.1); introduction to Rice's Theorem (Section 5.3).
- March 28: Rice's Theorem (Section 5.3).
- April 2: Enumerable languages (Sections 5.4 and 5.5).
- April 4: Language A is decidable if and only if both A and its complement are enumerable (Section 5.7); Halt is enumerable, but its complement is not enumerable (Section 5.7); both EQ_TM and its complement are not enumerable (Section 5.8); the set of all enumerable languages is countable (Section 5.6.1); the set of all languages is not countable (Section 5.6.2).
- April 9: Review: Chapter 7.