Introduction to Theory of Computation (COMP 3803)
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

• Introduction to Theory of Computation.

• 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.
  • Here is Assignment 1 as a pdf file.
  • Here is the LaTeX file.
  • Here and here are the figures.

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