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: Saturday April 24, 9-11am

- 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.
- Assignment 2 is due Sunday February 28, before 23:59.

- The midterm will be on Monday March 1, between 9:50 and 11:40am.
- Sign in to cuLearn on Monday March 1 by 9:50 and click the midterm link in Topic 3 to begin. Once you start, you have 90 minutes.
- It will be a multiple-choice exam with 18 questions. There will only be questions about regular languages. Thus, you are supposed to know everything that was done in class up to, and including, the pumping lemma, as well as the first two assignments.
- Here is the midterm from the
last time I taught this course. This was my first-ever
multiple-choice exam, and it is the only one I have for this course.
- Here are the answers.

- Saturday April 24, 9-11am.

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

- February 3:
- How to convert a DFA to a regular expression (Section 2.8.2).
- Video lecture 8.

- February 8:
- Pumping Lemma for regular languages (Section 2.9).
- Video lecture 9.

- February 10:
- Pumping Lemma, more examples (Section 2.9); introduction to context-free grammars (Section 3.1).
- Video lecture 10.

- February 15-19: Winter break.
- February 22:
- Context-free grammars (Section 3.1); examples of context-free grammars (Section 3.2).
- Video lecture 11.

- February 24:
- More examples of context-free grammars (Section 3.2); converting a DFA to a CFG, every regular language is context-free (Section 3.3); Chomsky Normal Form (Section 3.4; definition of CNF only, no details).
- Video lecture 12.

- March 1:
- Midterm, 10:00 - 11:30am.

- March 3:
- Deterministic pushdown automata; properly nested parentheses (Sections 3.5, 3.6.1).
- Video lecture 13.

- March 8:
- Deterministic pushdown automata (Section 3.6.2); nondeterministic pushdown automata (Section 3.6.3).
- Video lecture 14.

- March 10:
- Converting a context-free grammar to a nondeterministic pushdown automaton (Section 3.7); statement of the pumping lemma for context-free languages (Section 3.8); first example in Section 3.8.2.
- Video lecture 15.

- March 15:
- Proof of the pumping lemma (Section 3.8.1); example of a language that is not context-free (Section 3.8.2).
- Video lecture 16.

- March 17:
- One more example of a language that is not context-free (Section 3.8.2).
- Turing machines (Section 4.1); accepting palindromes using a one-tape Turing machine (Section 4.2.1).
- Video lecture 17.

- March 22:
- Accepting palindromes using a two-tape Turing machine (Section 4.2.2).
- More 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).
- Lecture 18.

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