CS 360: Introduction to the Theory of Computing  Fall 2019
David R. Cheriton School of Computer Science
Contents:
General Info,
Organization,
Announcements,
Resources,
Assignments,
Lectures,
University Policies
General Information
Time and Place: 1:00 PM  2:20 PM, Mon Wed, AL 124
First class is Wednesday September 4.
Instructor:
Jeffrey Shallit,
DC3134, x34804, (sorry, but to foil spammers, that's not a cutandpastable link)
Office hours: Tuesdays, 1 PM to 2 PM, or by appointment, or
just stop by whenever my office door is open.
On Tuesday September 10 I will be out of town, but I will hold office
hours via Skype at that time. My skype id is 'shallit'.
TAs:

Daniel Gabric, dgabric@uwaterloo.ca . Office hours: Tuesdays,
11:00 AM  12:00 PM in DC 2136B.

Vijay Subramanya, v7subram@uwaterloo.ca . Office hours:
Wednesdays 10AM12 Noon, in DC 2136A.
Credit:
Assignments 20%, Midterm 30%,
Final 50%. Your final mark is determined
from your marks on these,
and nothing else. In particular, there is no
requirement to pass the final in order to pass the course.
Turn in your assignments, in pdf format, via LEARN. You should prepare your
solutions using a document preparation system such as LaTeX or (ugh!)
Microsoft word. Do not write text by hand and scan.
However, for figures only (like automata),
feel free to sketch by hand and scan in the results. (If you're ambitious
and want to learn some new software, one easy thing to learn is
gv/dot for drawing automata.) One file per assignment, please.
Assignments will generally be given out on Wednesdays and will be due at 6 PM
on Thursdays, according to the following schedule:
Assignment number Handed out Due Marker
1 September 11 September 18 Vijay
2 September 18 September 25 Vijay
3 September 25 October 2 Vijay
4 October 2 October 9 Vijay
5 October 9 October 23 (two weeks) Daniel
6 October 23 October 30 Daniel
7 October 30 November 6 Daniel
8 November 6 November 13 Vijay
9 November 13 November 20 Vijay
10 November 20 November 27 Vijay
 Assignment 1. Handed out Wednesday September 11. Due 6 PM, Wednesday September 18.
Hand in to LEARN.
 Assignment 2. Handed out Wednesday September 18. Due 6 PM,
Wednesday September 25.
Hand in to LEARN.
 Assignment 3. Handed out Wednesday September 25. Due 6 PM,
Wednesday October 2.
Hand in to LEARN.
 Assignment 4. Handed out Wednesday October 2. Due 6 PM,
Wednesday October 9.
Hand in to LEARN.
 Assignment 5. Handed out Wednesday October 9. Due 6 PM,
Wednesday October 23.
Hand in to LEARN.
 Assignment 6. Handed out Wednesday October 23. Due 6 PM,
Wednesday October 30.
Hand in to LEARN.
 Assignment 7. Handed out Wednesday October 30. Due 6 PM,
Wednesday November 6.
Hand in to LEARN.
 Assignment 8. Handed out Wednesday November 6. Due 6 PM,
Wednesday November 13.
Hand in to LEARN.
Note: revised version posted 6:52 AM Thursday November 7 to
correct minor error.
Note: another revised version posted 4:38 AM Sunday November 10
to make it clear that $x$ is nonempty in question 1, and that
the TM's should be 1tape deterministic ones.
 Assignment 8. Handed out Wednesday November 13. Due 6 PM,
Wednesday November 20.
Hand in to LEARN.
The work you hand in must be your own.
Acknowledge any sources you have used. Unless specified otherwise,
you can always use any result from the notes (that we covered/assigned),
lecture, problem sets, or previous course, just by citing it.
Since solutions will be posted online almost immediately after the due date,
late assignments will not be accepted under any
circumstances. No extensions!
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 TA 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.
Enrichment
See this page for additional readings of
interest for each lecture.
Also, there's the Theory of Computing Hall of Fame.
We will not use the newsgroup
uw.cs.cs360. Instead we will use
Piazza for all
course announcements. So you should enroll yourself at your earliest
convenience. During Piazza discussions, please do not reveal the solutions
to the assignments by requesting or
offering extremely detailed advice. We'll delete
comments that reveal too much. Violations can result in
academic sanctions. Before posting questions, check previous
questions to make sure yours hasn't been asked before.
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.
Textbook:
There is no official textbook for the course. Instead, we'll use the
course notes prepared by Prof. John Watrous. These are wellwritten notes,
and have the significant advantage of being free. One
important thing to be
aware of, though: you must ignore statements in the course notes like
"I will never test your ability to perform routine
(and sometimes tedious) conversions like this" and
"You will not be tested on any of the details of
how this is proved". That's the way he taught the course, but is
not necessarily the way I will teach it.
Course Notes
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). There is one textbook on 3hour reserve in the
DC library:
 Hopcroft, Introduction to Automata Theory, Languages, and Computation, Call number QA267.H56 2007
Here is the tentative schedule of lectures. These may change a bit
as the course progresses, but probably not too much.

Lecture 1: Wednesday, September 4. Course overview and mathematical foundations.
Great Ideas of CS 360.
Practical applications of CS 360.
Symbols, words (strings), alphabets. Concatenation of words.
Formal definition of prefix, suffix, subword (subsequence, substring).
Formal inductive definition of x^{n}.
Reversal of string. Basic theorem of reversal:
(xy)^{R} = y^{R} x^{R}
(proof by induction on the length of a string).
Languages.
Reading: course notes, pp. 1112.
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 language is infinite, we mean it has infinitely many
elements.

Lecture 2: Monday, September 9. Guest lecture by Lukas Fleischer.
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. Reading: course notes, pp. 1620.

Lecture 3: Wednesday, September 11. Guest lecture by Lukas
Fleischer. Deterministic finite automata
and regular expressions.
The extended transition function: definition.
Definition of language recognized by a DFA.
Transition diagrams. Example:
personwolfgoat cabbage problem.
Example: strings over {0,1} representing, in base 2,
a number divisible by 3.
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 containing an odd number of b's.
Strings where all a's precede all b's, which precede all c's.
Same thing, but only nonempty strings (tricky!).
Reading: pp. 1820, pp. 3342 of course notes.

Lecture 4: Monday, September 16. 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: pp.
2332 of the course notes.

Lecture 5: Wednesday, September 18.
εtransitions. Statement of Kleene's theorem.
Proof of Kleene's theorem.
The state elimination method (handout).
Closure properties of regular languages: the class of regular language
is closed under the operations of union, concatenation, Kleene *,
intersection, complement, and reversal.
Reading: course notes, pp. 3344; 5556.

Lecture 6: Monday, September 23. Proving languages nonregular: the pumping
lemma.
Here are the languages
we studied:
 { 0^{n} 1^{n} : n ≥ 0 }
 PAL = { x ∈ {a,b}^{*} : x = x^{R} },
the palindromes language.
 PRIMES = { a^{p} : p prime }
All these are nonregular and can be proved so using the pumping lemma.
Reading: course notes, pp. 4553.

Lecture 7: Wednesday, September 25.
Handout: Nine errors students commonly
make when applying the pumping lemma.
Decidable properties of regular languages.
"Blackbox" versus "clearbox" algorithms for deciding language
emptiness, language infiniteness, whether two languages are
identical. See the handout.

Lecture 8: Monday, September 30.
The "blackbox" 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 firstorder 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).

Lecture 9: Wednesday, October 2.
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. If you improve either of the
known bounds, you get an automatic 100 for the course.
Introduction to contextfree grammars and languages. Reading:
course notes, pp. 6773. Formal definition. Examples.
Sentential forms, parse trees, ambiguity, and Chomsky normal form.
Reading: course notes, pp. 7585.

Lecture 10: Monday, October 7. 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.
Began handout on proving characterizations of grammars.

Lecture 11: Wednesday, October 9.
Finished the proof of correctness of the
last grammar in the handout on proving
characterizations of grammars. Long and hard!
Closure properties
of the class of contextfree 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.)
Reading: course notes,
pp. 7889.
Reading week: the week of October 1418. No classes.
Office hours will be held as usual.

Lecture 12: Monday, October 21 2019.
Intro to the pumping lemma for CFL's.
Proving languages noncontextfree.
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 contextfree languages.
Reading: course notes, pp. 9496
and 101105.

Lecture 13: Wednesday, October 23 2019.
An open problem: is the set of primitive words contextfree?
Introduction to pushdown automata (PDA's).
Instantaneous descriptions of PDA's. Formal
definition of acceptance in a PDA. Proof of one
direction of the theorem
that pushdown automata recognize exactly the class of CFL's.
Reading: course notes, pp. 97100, 107116. Note: the claim in the
course notes that "In this course we will treat the PDA model
as being optionalyou 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!

Lecture 14: Monday, October 28 2019.
Finished proof that PDA's recognize exactly the CFL's.
Proof that all regular languages are contextfree.
The class of CFL's is closed under intersection with a regular
language. Reading: course notes, pp. 107118.
Introduction to
the Turing machine model of computation.

Lecture 15: Wednesday, October 30 2019.
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 "onesided" tape.
Reading: course notes,
pp. 119134.

Lecture 16: Monday, November 4 2019.
Definition of Turingrecognizable (aka "recursively enumerable")
and Turingdecidable (aka "recursive").
Variants of Turing machines and encoding objects as strings.
Turing machine with "onesided" tape. Turing machine with multipletrack
tape. Turing machine with multiple tapes.
Encodings of strings, numbers, vectors, matrices, graphs.
Reading: course notes, pp. 131143, 177178.

Lecture 17: Wednesday, November 6 2019.
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
Turingdecidable languages and the set of Turing recognizable
languages is countable.
Reading: course notes, pp. 516, 145157.

Lecture 18: Monday, November 11 2019.
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.
Turingdecidable languages vs. Turingrecognizable.
Recursive versus recursively enumerable. The universal TM.
Here is a handout about Turingdecidable and Turingrecognizable
languages.

Lecture 19: Wednesday, November 13 2019.
The RAM model (model of a general purpose computer, similar
to assembly language). Slides:
Sketch of proof that the
RAM model can be simulated by a Turing machine.
Explicit examples of unrecognizable and
undecidable languages: DIAG, A_{TM}.
Reading: course notes, pp. 157161.

Lecture 20: The HALT language. Notes:
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.
The L_{EMPTY}
language (consisting of
those encodings of TM's M such that L(M) = ∅)
is not Turingdecidable. In fact, it's not even
Turingrecognizable! Important theorem:
If L is Turingrecognizable and its complement is,
then L is Turing decidable. 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.
Reading: course notes, pp. 163171.

Lecture 21:
Closure properties of Turingrecognizable and Turingdecidable languages.
Enumerators and recursively enumerable languages.
Computable functions and reductions. Example of an uncomputable
function: the busy beaver problem.
Further discussion of Turing machines. Intro to the Post
correspondence problem (PCP).
Reading: course notes, pp. 171181.

Lecture 22: Unsolvable problems. More on PCP.
Using PCP to prove that it is undecidable, in
general, whether a given grammar
is ambiguous.
Introduction to resourcebounded computation: P.
Reading: course notes, pp. 183190. Course evaluations.

Lecture 23: More on resourcebounded computation.
The class of languages DTIME (f). Definitions of P and EXP.
The timehierarchy theorem (sketch only). P ≠ EXP. Definition
of NP. The two different definitions of NP are the same: one
based on nondeterministic TM's, the other based on short, easilyverifiable
certificates. Example of a language in NP:
{ (n,B) : there exists a divisor of n between 2 and B inclusive }.
Reading: course notes, pp. 191199.

Lecture 24: P versus NP.
More examples of languages in NP.
Polynomialtime reductions.
Definition of NPhard and NPcomplete.
The CookLevin theorem. Course wrapup.
Reading: course notes, pp. 200219.
What to know for the final exam.
Prize for the highest average in the course so far.
Plagiarism
Plagiarism is a serious offence. The penalties can be severe.
To avoid plagiarism accusations, do not copy other people's work, and cite all references that you use.
If you work with others,
only discuss general aspects of the course material,
not specific solutions. Write up the solutions yourself, not in groups.
University Required Text
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/academicintegrity/ 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/academicintegrity/]
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:
 Lecture content, spoken and written (and any audio/video recording thereof);
 Lecture handouts, presentations, and other materials prepared for the course (e.g., PowerPoint slides);
 Questions or solution sets from various types of assessments (e.g., assignments, quizzes, tests, final exams); and
 Work protected by copyright (e.g., any work authored by the instructor or TA or used by the instructor or
TA with permission of the copyright owner).
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.