Time and Place: Online.
Course begins Tuesday September 8 2020.
Instructor:
Jeffrey Shallit,
DC3134, x34804, (sorry, but to foil spammers, that's not a cut-and-pastable link)
Office hours: TBA
TAs:
Important: if something is not working out for you, let me know your suggestions for how the course could be better!
Your final mark is just computed from the above four components. There is no need to pass any individual component to pass the course.
In all assignments and exams, unless directed otherwise, you can always use any result from class or course notes (that we covered/assigned) or previous assignments just by quoting it.
Assignments will generally be given out on Wednesdays and will be due at 6 PM on Wednesdays, according to the following schedule:
Assignment number Handed out Due Marker 1 September 9 September 16 2 September 16 September 23 3 September 23 September 30 4 September 30 October 7 5 October 7 October 21 6 October 21 October 28 7 October 28 November 4 8 November 4 November 11 9 November 11 November 18 10 November 18 November 25 11 November 25 December 2
Since solutions will be posted online almost immediately after the due date, late assignments will not be accepted under any circumstances. No extensions! If you get a doctor's note you can be exempted from an assignment.
In all assignments and exams, unless otherwise directed, you are expected to justify any claims that you make. The level of explanation we generally expect is "enough to convince a skeptical TA". You can always use any result proved in class, or in the course notes, just by citing it.
If you have a question or complaint about how your assignment or exam was marked, please start by contacting the person who marked your assignment or exam. This can be determined either by consulting the initials written on your assignment, or by looking on the course home page. Make arrangements to see this TA to discuss your assignment. You must make initial contact with the TA within one week from the day your assignment is returned.
If you are not satisfied after talking with the TA, contact the instructor.
On the last day of classes, a prize will be given to the student(s) with the highest average so far.
Also, there's the Theory of Computing Hall of Fame.
Similarly, do not solicit hints or provide hints about how to solve the homework problems on other bulletin boards, such as Facebook. Violations can result in academic sanctions.
Marks will be available through LEARN.
Almost any textbook on "theory of computing" or "theory of computation" will work as well (although not everyone uses exactly the same model or exactly the same notation). For example:
Note: when we say a string is infinite, we mean it has infinitely many symbols. (But we never discuss infinite strings in this course!) When we say a set or language is infinite, we mean it has infinitely many elements.
Languages and deterministic finite automata. Post's problem (see the enrichment page): start with a string. If it begins with 0, concatenate 00 on the end. If it begins with 1, concatenate 1101 on the end. In both cases, next delete the first three symbols. Starting with any string, and applying these operations, do you eventually return to a string you already saw, or do you go forever, generating a new string at each step? Nobody knows any example of the latter, but nobody has proved it can't happen.
Languages: a set of strings. Set notation. Union, intersection, set difference, complement of languages. De Morgan's laws. Concatenation of languages: definition, properties (don't make the mistake of thinking that L · ∅ = L !!!). Concatenation distributes over union. Introduction to deterministic finite automata (DFA's). Parts of a DFA. Language accepted by a DFA.
Readings for the week: course notes, pp. 11-12, 16-20.
Nondeterministic finite automata (NFA). Definition of NFA. The extended transition function δ^{*}. Example (NFA that recognizes those strings with 1 in n positions from the end). Example: NFA that recognizes those strings with aabab as a subword. Proof: NFA's recognize the same class of languages as DFA's: the subset construction.
Reading for the Week: pp. 18-20, pp. 23-42 of course notes.
Proving languages nonregular: the pumping lemma. Here are the languages we studied:
Reading for the week: course notes, pp. 33-56.
The "black-box" algorithm for deciding, given two regular languages, whether they are equal. See the handout.
How to prove L = { a^{m} b^{n} : m ≠ n } nonregular? You can do it using the pumping lemma, but it's hard! (try it). Much easier: assume L regular, apply some closure properties of the class of regular languages (which preserve regularity) to L to turn it into something you already know is nonregular, and thus get a contradiction.
Introduction to Presburger arithmetic: the theory of natural numbers with addition. Prenex normal form. A good reference for Presburger is Sipser's book, Introduction to the Theory of Computation, section 6.2. But Presburger is mostly "enrichment material" that I won't test you on. Theorem: the first-order theory of natural numbers with addition is complete (all true statements are provable) and decidable (there exists an algorithm to decide whether a given statement is true or false).
Introduction to context-free grammars and languages. Formal definition. Examples.
Sentential forms, parse trees, ambiguity, and Chomsky normal form.
More about Chomsky normal form. Nullable variables. Finding the nullable variables. Removing unit productions.
Application of Chomsky normal form: every word of length n derivable in a CNF grammar is derivable in exactly 2n - 1 steps.
A handout on proving characterizations of grammars.
Reading for the week: course notes, pp. 67-85.
Intro to the pumping lemma for CFL's. Proving languages non-context-free. Proof. Examples of use. Important observations: the intersection of two CFL's need not be a CFL; the complement of a CFL need not be a CFL. Proof of the pumping lemma for context-free languages.
Reading for the week: course notes, pp. 78-89, 94-96, 101-105.
Finished proof that PDA's recognize exactly the CFL's. Proof that all regular languages are context-free. The class of CFL's is closed under intersection with a regular language.
Reading: course notes, pp. 97-100, 107-118. Note: the claim in the course notes that "In this course we will treat the PDA model as being optional--you will not be asked questions that are directly about this model or that require you to use it, but you are free to make use of it if you choose" does not apply to this version of the course!
More on the Turing machine model of computation. Example of a Turing machine. Formal definition of Turing machine: configurations, starting configuration, halt state, reject state, failing to halt. Difference between recognition and deciding. Turing machines with "one-sided" tape.
Definition of Turing-recognizable (aka "recursively enumerable") and Turing-decidable (aka "recursive"). Variants of Turing machines and encoding objects as strings. Turing machine with "one-sided" tape. Turing machine with multiple-track tape. Turing machine with multiple tapes. Encodings of strings, numbers, vectors, matrices, graphs.
Reading for the week: course notes, pp. 119-143, 177-178.
Countability of sets. The real numbers are not countable. The set of all languages is not countable. The set of Turing-decidable languages and the set of Turing recognizable languages is countable.
Encodings of DFA's, PDA's, CFG's, Turing machines. Properties of a good encoding: (a) it should be possible to determine if some string is or is not a valid encoding (b) it should be possible to unambiguously decode a string to the object it represents (c) when another string s is concatenated on the end, it should be possible to determine where the encoded object ends and s begins. Turing-decidable languages vs. Turing-recognizable. Recursive versus recursively enumerable. The universal TM.
Here is a handout about Turing-decidable and Turing-recognizable languages.
Reading for the week : course notes, pp. 5-16, 145-157.
Reductions. Using reductions to prove languages not Turing-decidable. Handout: Is Turing's Unsolvability Theorem Applicable to the Real World?. Example of a TM with only 7 states that runs for more than 10^{35000} steps before halting. Computable functions and reductions. Example of an uncomputable function: the busy beaver problem. Important theorem:
Reading for the week: course notes, pp. 157-171.
More undecidable problems: matrix problems and tiling problems. Time complexity. The class DTIME(f(n)). Introduction to resource-bounded computation: the class P. Definitions of P and EXP.
Reading for the week: course notes, pp. 171-190.
P versus NP. More examples of languages in NP. Polynomial-time reductions. Definition of NP-hard and NP-complete. The Cook-Levin theorem. Course wrap-up. What to know for the final exam. Prize for the highest average in the course so far. Reprise of the Great Ideas of the course. Where to go next after this course.
Reading for the week: course notes, pp. 191-219.
Academic Integrity: In order to maintain a culture of academic integrity, members of the University of Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility. [Check https://uwaterloo.ca/academic-integrity/ for more information.]
Grievance: A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70, Student Petitions and Grievances, Section 4. When in doubt please be certain to contact the department's administrative assistant who will provide further assistance.
Discipline: A student is expected to know what constitutes academic integrity [check https://uwaterloo.ca/academic-integrity/] to avoid committing an academic offence, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offence, or who needs help in learning how to avoid offences (e.g., plagiarism, cheating) or about 'rules' for group work/collaboration should seek guidance from the course instructor, academic advisor, or the undergraduate Associate Dean. For information on categories of offences and types of penalties, students should refer to Policy 71, Student Discipline. For typical penalties check Guidelines for the Assessment of Penalties.
Appeals: A decision made or penalty imposed under Policy 70 (Student Petitions and Grievances) (other than a petition) or Policy 71 (Student Discipline) may be appealed if there is a ground. A student who believes he/she has a ground for an appeal should refer to Policy 72, Student Appeals.
Note for Students with Disabilities: AccessAbility Services, located in Needles Hall, Room 1401, collaborates with all academic departments to arrange appropriate accommodations for students with disabilities without compromising the academic integrity of the curriculum. If you require academic accommodations to lessen the impact of your disability, please register with AccessAbility Services at the beginning of each academic term.
Intellectual Property: Students should be aware that this course contains the intellectual property of their instructor, TA, and/or the University of Waterloo. Intellectual property includes items such as:
Course materials and the intellectual property contained therein, are used to enhance a student's educational experience. However, sharing this intellectual property without the intellectual property owner's permission is a violation of intellectual property rights. For this reason, it is necessary to ask the instructor, TA and/or the University of Waterloo for permission before uploading and sharing the intellectual property of others online (e.g., to an online repository).
Permission from an instructor, TA or the University is also necessary before sharing the intellectual property of others from completed courses with students taking the same/similar courses in subsequent terms/years. In many cases, instructors might be happy to allow distribution of certain materials. However, doing so without expressed permission is considered a violation of intellectual property rights.
Please alert the instructor if you become aware of intellectual property belonging to others (past or present) circulating, either through the student body or online. The intellectual property rights owner deserves to know (and may have already given their consent).
Here is a page we are required to give you, even though all the same info is above.