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 cut-and-pastable 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'.


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

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.


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 well-written 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 3-hour reserve in the DC library:


Here is the tentative schedule of lectures. These may change a bit as the course progresses, but probably not too much.


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/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.