CS 360: Introduction to the Theory of Computing (Spring 2024)

David R. Cheriton School of Computer Science

Course Outline

If you wish to enroll in the course, either use QUEST or contact a computer science advisor (not a mathematics advisor). The instructor cannot help with registration issues. To contact your instructor about other matters, see below.

Office Hours

For any questions concerning the course material, please connect with me during our scheduled office hours. Times listed below are in Waterloo (Eastern) Time. Office hours will be held in DC 3108, or on Microsoft Teams (in-person students will take precedence over students on MS Teams, if there is a conflict). To meet on MS Teams, please post a note in the waiting room channel, linked below. If the hours posted below do not suit you, then please contact me directly to schedule an appointment.

name	time	waiting room
Collin Roberts (cd2rober@uwaterloo.ca)	Wednesdays, 14:00-15:00, Fridays, 11:00-12:00, or by appointment.	MS Teams

Grading Scheme

Marked Quizzes on LEARN	10%
Crowdmark Assignments	30%
Mid-Term Exam (2024-06-27, 16:30-18:20)	20%
Final Exam (will be scheduled by the Registrar)	40%

Notes:

The work you submit must be your own and written in your own words, with citations to any sources that you have used. You may discuss the assignment questions verbally with others but should come away from these discussions with no electronic or written records.
You must pass the weighted Exam portion of the course (the Mid-Term Exam and the Final Exam) in order to pass the course.
Here are the details about how the marked quizzes will work:
- There will be a marked quiz due in each week when there will not be a Crowdmark assignment due or a mid-term examination. The due dates for the marked quizzes are displayed on the course schedule page.
- No late submissions of marked quizzes will be accepted.
- From the time you start taking the marked quiz, you will have one hour in which to complete it. You must submit your quiz before this hour elapses and before the due date and time to receive credit.
- You will have a maximum of two attempts at each marked quiz. If you make two attempts, then the higher grade will count.
- Your grading for each marked quiz will be displayed on LEARN after the due date and time has passed.
- Your marked quiz will be randomly customized for you. We will ensure that the variations of any given question are all of the same difficulty.
Here are the details about how late marked Crowdmark assignments will be handled:
- For full credit, you must submit your solutions by the specified due date and time.
- A late penalty will be applied for each hour that you are late in submitting.
- There will be a 5% penalty per hour that you are late in submitting.
- If you have submitted anything before the deadline, then Crowdmark will not let you re-submit after the deadline passes. This means that you must decide whether to exercise your option to submit late before the deadline, and refrain from making a partial submission in this case.

Resources

All course materials will be posted on this website or the LEARN site. Assignments, and model solutions will also be provided. You will answer the marked quizzes on LEARN.

The recommended course textbook is Introduction to Automata Theory, Languages, and Computation, 3^rd Edition, by Hopcroft, Motwani and Ullman. The call number for the textbook at the UW Davis Library is QA267.H56 2007.

There are many books available on automata theory and formal languages. All these may be relevant to certain parts of the course and, for those, they could be useful background reading. Other sources will likely differ in their precise notation. For submissions to the course, always use the notation from our notes and the course text.

Textbook Details from the Bookstore

Hardcover
Title : Introduction to Automation Theory, Languages and Computation
Author: Hopcraft
ISBN : 9780312455369
Price : $249.99
The printed book can be ordered online from wstore.ca. You can log in to UWaterloo BookLook, using your UWaterloo email and password, to view your personalized booklist and add items directly to your shopping cart.
A common list of online questions, such as shipping rates and returns, can be found on our website at https://wstore.ca/help.
If you need assistance with your online order, please email wstore@uwaterloo.ca. A member of our team will reach out as soon as possible.

Mental Health

If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support.

Note for students with disabilities

UW's AccessAbility Services office (AAS), 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 the AAS at the beginning of each academic term.

Academic Integrity and Students with Disabilities

Academic Policies

This course adheres to the UW Senate's statement of academic integrity, specifically:

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. All members of the UW community are expected to hold to the highest standard of academic integrity in their studies, teaching, and research.

The Office of Academic Integrity's website contains detailed information on UW policy for students and faculty. This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in—and out of—the classroom.

Grievances

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.

Discipline

A student is expected to know what constitutes academic integrity, to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about rules for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. When misconduct has been found to have occurred, disciplinary penalties will be imposed under Policy 71—Student Discipline. For information on categories of offenses and types of penalties, students should refer to Policy 71—Student Discipline.

Avoiding Academic Offenses

For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Guidelines.

Appeals

A student may appeal the finding and/or penalty in a decision made under Policy 70—Student Petitions and Grievances (other than regarding a petition) or Policy 71—Student Discipline if grounds for an appeal can be established. Read Policy 72—Student Appeals.