CS 360: Introduction to the Theory of Computing  Fall 2017
David R. Cheriton School of Computer Science
Contents:
General Info,
Organization,
Announcements,
Resources,
Assignments,
Lectures,
University Policies
General Information
Instructors:
Jeffrey Shallit,
DC3134, x34804, (sorry, but to foil spammers, that's not a cutandpastable link)
Office hours: Wednesdays 1:30  2:20 PM in DC 3134, or when my office door is open, or by appointment.
TAs:

Jian Li, j493li@uwaterloo.ca . Office hours: 2 PM to 3 PM, Thursdays, in DC 2102.

Vijay
Subramanya, v7subram@uwaterloo.ca . Office hours: Wednesdays
from 11 AM to Noon, DC 2569 .
Time and Place:
First class is THURSDAY, SEPTEMBER 7!
 Section 1: Tuesdays & Thursdays, 10:00 AM  11:20 AM, MC 4040
Credit:
Assignments 20%, 2 InClass Exams 20% Each,
Final 40%. 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.
 Assignments 20%  see dates below.
 InClass Exams:
For both exams,
you can bring one 8.5" x 11" sheet of paper to the exam with anything on it (written,
printed, anything). Both
sides of the paper
may be used. No other aids allowed. In particular, no computers,
calculators, tablets, phones, or electronic devices.
Do not bring phones!

Exam 1: Thursday, October 12, in class. It will cover all the material
in Lectures 19. See this page for more info
about what I expect you to know.

Exam 2: Thursday, November 9, in class. It will cover the material in
Lectures 1117.
See this page for more info
about what I expect you to know.
 Final Exam 40%. Thursday, December 7 2017, 12:30  3:00 PM,
STC 0040. See this page for more info
about what I expect you to know.
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.
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 Thursdays and will be due at 5 PM
on Thursdays, according to the following schedule:
Assignment number Handed out Due Marker
1 September 7 September 18 Jian Li
2 September 14 September 21 Vijay Subramanya
3 September 21 September 28 Jian Li
4 September 28 October 5 Vijay Subramanya
5 October 12 October 19 Vijay Subramanya
6 October 19 October 26 Jian Li
7 October 26 November 2 Vijay Subramanya
8 November 2 November 16 Jian Li
9 November 16 November 23 Vijay Subramanya
10 November 23 November 30 Jian Li
 Problem Set 1, handed out September 7, due September 18.
latex source, pdf
 Problem Set 2, handed out September 14, due September 21.
latex source, pdf
(Updated at 3:37 PM on Thursday September 14 to reflect
the fact that in 2 (b) the "do not contain two" should be understood
as meaning "do not contain two or more".)
(Updated again at 4:07 PM on Thursday September 14 to give you
a recursive definition of length of a string.)
(Updated again at 4:16 PM on Tuesday September 19, to make the bonus
question a little more specific.)
 Problem Set 3, handed out September 21, due September 28.
latex source, pdf
 Problem Set 4, handed out September 28, due October 5.
latex source, pdf
 Problem Set 5, handed out October 10, due October 19.
latex source, pdf
 Problem Set 6, handed out October 19, due October 26.
latex source, pdf
 Problem Set 7, handed out October 26, due November 2.
latex source, pdf,
pda.pdf diagram
 Problem Set 8, handed out November 2, due November 16.
latex source, pdf
 Problem Set 9, handed out November 16, due November 23.
latex source, pdf
 Problem Set 10, handed out November 23, due November 30.
latex source, pdf
Modified, 7 AM, November 25, to add hint for Q2.
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".
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.
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, Thursday September 7: 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).
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, Tuesday September 12: 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. Note:
Assignment 1 due date moved to Monday, September 18 at 5 PM.

Lecture 3, Thursday September 14: 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.
Assignment 1 due date moved to Monday, September 18 at 5 PM.
You can submit multiple times, only the last is saved.
Assignment 2 now available.

Lecture 4, September 19: 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. εtransitions.
Statement of Kleene's theorem.

Lecture 5, September 21: 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, September 26: Proving languages nonregular: the pumping
lemma. Handout: Nine errors students commonly
make when applying 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.
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.
Reading: course notes, pp. 4553.

Lecture 7, September 28: Decidable properties of regular languages.
"Blackbox" versus "whitebox" algorithms for deciding language
emptiness, language infiniteness, whether two languages are
identical.
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.

Lecture 8, October 3: Finished the proof, using automata,
that the 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 contextfree grammars and languages. Reading:
course notes, pp. 6773.

Lecture 9, October 5: Parse trees, ambiguity, and Chomsky normal form.
Began handout on proving characterizations of grammars.
Reading: course notes, pp. 7585.

October 10: No class (study day)

Lecture 10, October 12: InClass Exam #1, covering lectures 19.
See this page for a longer discussion
about what you need to know.

Lecture 11, October 17: Remarks on InClass Exam #1: if you got anything
wrong on problems 1 and 2 (except 1 (e)) you need to review basic
definitions and make sure you understand them!
Finished the proof of correctness of the
last grammar in the handout on proving
characterizations of grammars. Another example: grammar for
arithmetic expressions. Chomsky normal form. Closure properties
of the class of contextfree languages: closure under
union, concatenation, star. Reading: course notes,
pp. 7889.

Lecture 12, October 19: Showing that Pref(L) is contextfree if
L is. (The proof suggested in the course notes is largely correct,
but needs to be fixed as follows: first, remove from G all variables
that do not generate terminal strings.)
Proving languages noncontextfree; the
pumping lemma for CFL's. Proof. Examples of use. Observations:
the intersection of CFL's need not be a CFL; the complement of a
CFL need not be a CFL. Reading: course notes, pp. 9496
and 101105.

Lecture 13, October 24: Proof of the pumping lemma for contextfree
languages. Proof that all regular languages
are contextfree. Introduction to pushdown automata (PDA'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, October 26: More on pushdown automata. Instantaneous
descriptions of PDA's. Formal
definition of acceptance in a PDA. Sketch of proof
that pushdown automata generate exactly the class of CFL's.
The class of CFL's is closed under intersection with a regular
language. Reading: course notes, pp. 107118. Note: the claim
in the course notes
beginning with "In this course we will treat the PDA model
as being optional..."
does not apply to this version of the course.

Lecture 15, October 31: Introduction to
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.
Definition of Turingrecognizable (aka "recursively enumerable")
and Turingdecidable (aka "recursive"). Reading: course notes,
pp. 119134.

Lecture 16, November 2:
Variants of Turing machines and encoding objects as strings.
Turing machine with "onesided" tape. Turing machine with multipletrack
tape. Turing machine with multiple tapes.
Nondeterministic Turing machines.
Reading: course notes, pp. 131143, 177178.

Lecture 17, November 7: Finished discussion of nondeterministic
Turing machines. Encodings of strings, numbers, vectors, matrices,
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. Countability. The real numbers are not countable.
Reading: course notes, pp. 516, 145157.

Lecture 18, November 9: InClass Exam #2, covering lectures 1117.
See this page for a longer discussion
about what you need to know.

Lecture 19, November 14:
The RAM model. Slides:
Sketch of proof that the
RAM model can be simulated by a Turing machine. Proving that there
are uncountably many languages, but only countably many
Turingrecognizable languages (so there is at least one language
that is not Turingrecognizable). Explicit examples of unrecognizable and
undecidable languages: DIAG, A_{TM}.
Reading: course notes, pp. 157161.

Lecture 20, November 16: 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, November 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, November 23: 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, November 28: 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, November 30: 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.
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.