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


Organization

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

Office hours: Wednesdays 1:30 - 2:20 PM in DC 3134, or when my office door is open, or by appointment.

TAs:

Time and Place:

First class is THURSDAY, SEPTEMBER 7!

Credit: Assignments 20%, 2 In-Class 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.

In all assignments and exams, unless directed otherwise, you can always use any result from class or course notes 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 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

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, lecture, 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.


Announcements

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.


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). There is one textbook on 3-hour reserve in the DC library:



Lectures

Here is the tentative schedule of lectures. 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.