Time and Place: Online.
Course begins Tuesday September 8 2020. Join me on Zoom on Tuesday, September 8, at 8 PM EDT (8 AM Wed Sep 9 in Beijing) to introduce yourself and ask any questions about how the course will be run. The URL and password to join are posted on LEARN.
Instructor:
Jeffrey Shallit,
DC3134, x34804, (sorry, but to foil spammers, that's not a cut-and-pastable link)
Office hours: 11 AM - Noon Tuesdays, on Zoom. Link is posted each week on Piazza.
TAs:
Adam Jaffe, ,
ajaffe@uwaterloo.ca .
Office hours: 7-8 PM EDT Mondays, on Zoom. Link is posted each
week on Piazza.
Joseph Meleshko, ,
jmeleshko@uwaterloo.ca .
Office hours: 11 AM - Noon EDT Mondays, on Zoom. Link is posted each
week on Piazza.
The course material is distributed in several different ways:
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. Same with things from previous courses.
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 Adam J. 2 September 16 September 23 Adam J. 3 September 23 September 30 Joseph M. 4 September 30 October 7 Joseph M. 5 October 7 October 21 Adam J. 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
Solutions to these problem sets can be found on LEARN. These solutions are for your self-study only. I ask that you do not archive solutions online or post them anywhere. By doing so you would deprive future students of the pleasure of working on the problems themselves, unaided.
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.
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.
Readings for the week: course notes, pp. 11-12, 16-20. Quiz 1, September 14.
Problem Set 1 was distributed and is due on Wed Sep 16. Hand in to LEARN.
Slides for the week:
Introduction to deterministic finite automata (DFA's). Parts of a DFA. The extended transition function: definition. Definition of language recognized by a DFA. Transition diagrams. Example: person-wolf-goat cabbage problem. Example: strings over {0,1} representing, in base 2, a number divisible by 3.
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). Proof: NFA's recognize the same class of languages as DFA's: the subset construction. ε-transitions.
Regular expressions and their operations: union, concatenation, Kleene * . Examples: strings over {a,b} containing an occurrence of aa; not containing an occurrence of aa (tricky). Strings where all a's precede all b's, which precede all c's. Same thing, but only nonempty strings (tricky!). The state elimination method (handout).
Slides for the week:
Reading for the Week: pp. 18-20, pp. 23-42 of course notes. Quiz 2, September 21.
Proving languages nonregular: the pumping lemma. Here are some of the languages we studied:
The separating words problem: given two strings x and y of length ≤ n, what is the smallest number of states in a DFA accepting one but not the other? Lower and upper bounds are known, but they are widely separated.
Slides for the week:
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.
Decidable properties of regular languages. "Black-box" versus "clear-box" algorithms for deciding language emptiness, language infiniteness, whether two languages are identical. See the handout.
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. 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).
Slides for the week:
Reading for the week: course notes, pp. 55-65. Quiz 4, October 5.
Sentential forms, parse trees, ambiguity.
Chomsky normal form. Nullable variables. Finding the nullable variables. Removing unit productions. Identifying useless symbols.
Application of Chomsky normal form: every word of length n derivable in a CNF grammar is derivable in exactly 2n - 1 steps. Hence the following problem is decidable: given a grammar G and a word w, does G derive w?
A handout on proving characterizations of grammars.
Slides for the week:
Reading for the week: course notes, pp. 67-85.
Here is a list of 20 sample questions for the oral midterm. Almost certainly I will ask you at least one question from this list (as well as others, of course).
Closure properties of the class of context-free languages: closure under union, concatenation, star, reversal, prefix. Basic idea: take a grammar for the language and modify it somehow. (The proof suggested in the course notes for prefix is largely correct, but needs to be fixed as follows: first, remove from G all variables that do not generate terminal strings.)
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.
Application of the pumping lemma to decision problems about CFG's. For example, given a grammar G, is L(G) empty? Given a grammar G, is L(G) infinite?
An open problem: is the set of primitive words context-free?
Slides for the week:
Reading for the week: course notes, pp. 78-89, 94-96, 101-105.
Quiz #5 on Week 5 material, October 19.
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!
Quiz #6 on Week 6 material, October 26.
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.
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.
Nondeterministic Turing machines. Example. Formal definition. Simulating an NTM by a DTM.
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.
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.
Explicit examples of unrecognizable and undecidable languages: DIAG, A_{TM}. The HALT language. Enumerators and recursively enumerable languages: a language is Turing-decidable iff its members can be enumerated in radix order (shortest strings first, then in alphabetical order within length). A language is Turing-recognizable iff its members can be enumerated (not necessarily in radix order). The "dovetailing technique": for each n, run TM on the i'th possible input for j steps, over all i and j such that i + j = n.
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.
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.
You are forbidden to use solution sharing sites, such as Chegg and Slader.
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.