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 2:30  3:30 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 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.

Exam 2: Thursday, November 9, in class. It will cover the material in
Lectures 1117.
 Final Exam 40%.
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
4 September 28 October 5
5 October 12 October 19
6 October 19 October 26
7 October 26 November 2
8 November 9 November 16
9 November 16 November 23
10 November 23 November 30
 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
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 textbook, notes, 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).
Reference: course notes, pp. 1112.

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. Reference: 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!).
Reference: 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.

Lecture 6, September 26: Proving languages nonregular: the pumping
lemma. Handout: Nine errors students commonly
make when applying the pumping lemma. Applications.

Lecture 7, September 28: Decidable properties of regular languages.
"Blackbox" versus "whitebox" algorithms.

Lecture 8, October 3: Contextfree grammars and languages

Lecture 9, October 5: Parse trees, ambiguity, and Chomsky normal form

October 10: No class (study day)

Lecture 10, October 12: InClass Exam #1, covering lectures 19

Lecture 11, October 17: Closure properties for contextfree languages

Lecture 12, October 19: Proving languages noncontextfree

Lecture 13, October 24: Further discussion of contextfree languages

Lecture 14, October 26: Further discussion of contextfree languages

Lecture 15, October 31: The Turing machine model of computation

Lecture 16, November 2: Variants of Turing machines and encoding objects as strings

Lecture 17, November 7: Decidable languages

Lecture 18, November 9: InClass Exam #2, covering lectures 1117

Lecture 19, November 14: Undecidable languages

Lecture 20, November 16: Computable functions and reductions

Lecture 21, November 21: Further discussion of Turing machines

Lecture 22, November 23: Unsolvable problems

Lecture 23, November 28: Introduction to resourcebounded computation

Lecture 24, November 30: P versus NP; course wrapup
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.