CS 360: Introduction to the Theory of Computing -- Fall 2021

David R. Cheriton School of Computer Science

Contents: General Info, Organization, Evaluation, Assignments, Enrichment, Keeping in Touch, Resources, Week by Week, University Policies

General Information


Time and Place: Online, via Zoom. No physical class. Meets 10:00-11:20 Mondays and Wednesdays. First class is Wednesday, September 8 2021. If you are enrolled in the class, you should have by now received a Zoom link via e-mail. If you have checked your e-mail and not received such a link, contact Prof. Shallit by e-mail.

All lectures will be recorded and available on LEARN.

Instructor: Jeffrey Shallit, (sorry, but to foil spammers, that's not a cut-and-pastable link)

Office hours via Zoom: Mondays, 7 PM, at the same Zoom link as for the class (posted on Piazza), or by appointment. You can also contact me anytime I am logged on (roughly 7 AM to 7 PM most days) via skype (userid = shallit). I am happy to help you there. Finally, after each lecture on Zoom I will stick around to answer questions until the last student has left.


Daniel Gabric, dgabric@uwaterloo.ca. Office hours via Zoom: Tuesdays, 7 PM--8PM. Link posted on Piazza.  

Yuqi Liu, y899liu@uwaterloo.ca. Office hours via Zoom: Tuesdays, 10 AM--11 AM. Link posted on Piazza.  

How the course material is distributed

The courses will be presented online through Zoom, but videos of the lectures will be posted.

The course material is distributed in several different ways:

Each week you should do the assigned readings and attend the lecture or watch the video of the lecture. Then do the easy quiz (more info below), work on the problems in the problem set, and post to Piazza or attend office hours if you have questions.

Important: if something is not working out for you, let me know your suggestions for how the course could be better!


Evaluation consists of four components: The quizzes together are worth 15%, the problem sets in total are worth 40%, the oral midterm is worth 15%, and the oral final is worth 30%. For the problem sets, the lowest of 11 marks will be dropped (i.e., you will only be marked out of 10 problem sets).

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.


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. Here is a file of tips for using latex: latextips.txt
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. You can submit multiple times before the due date, but only the last submission is kept.

All problem sets have 3 problems, each worth 10 marks. Typically, the first is easy, the second is middling, and the third is hardest.

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 8     September 15	Daniel Gabric
	  2             September 15    September 22
	  3             September 22    September 29
	  4             September 29    October 6
	  5             October 6       October 20 
	  6             October 20      October 27
	  7             October 27      November 3
	  8             November 3      November 10
	  9             November 10     November 17
	  10            November 17     November 24
	  11            November 24     December 1

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.

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 courses, 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! 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.


See this page for additional readings of interest for each lecture.

Also, there's the Theory of Computing Hall of Fame.

Keeping in Touch

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.

Do not solicit hints or provide hints about how to solve the homework problems on Piazza or other bulletin boards, such as Facebook. Doing so 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, the Spring 2017 version. (Don't use more recent versions that you can find online, which make some changes I don't like!) 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). For example:

Week by Week

Here is the tentative schedule of material we'll cover. 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.

You are forbidden to use solution sharing sites, such as Chegg and Slader.

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.