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

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


Organization

Time and Place: Online.

Course begins Tuesday September 8 2020.

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

Office hours: TBA

TAs:

How the course material is distributed

The course material is distributed in several different ways: Each week you should do the assigned readings, watch the videos (pausing when I suggest to do so, and trying the problems in the videos) --or if you prefer, just read the accompanying slides. Then do the easy quiz (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

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.

Assignments

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 Wednesdays, according to the following schedule:

Assignment number	Handed out	 	Due             Marker
	1		September 9		September 16               
	2              	September 16		September 23 
	3               September 23		September 30
	4               September 30		October 7
	5		October 7		October 21              
	6               October 21		October 28 
	7               October 28		November 4
	8               November 4		November 11
	9		November 11		November 18               
	10              November 18		November 25
	11		November 25		December 2

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


Enrichment

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.

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.


Resources

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

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.