This course provides accelerated coverage of the material from CS 360, including finite automata and regular languages, context free grammars and pushdown automata, Turing machines, and undecidability. In addition, topics from complexity theory are covered, including time and space complexity, hierarchy theorems, and complete problems for various classes.
The primary textbook for the class is:
Previous editions of the textbook are also acceptable. Another useful, though not required, reference for the second half of this course is:
The assignments will be listed here as they become available. They will be made available every Thursday and are due in class the following Thursday.
The assignments are due in class on their respective due dates. No late assignments will be accepted.
Collaboration with classmates when completing the assignments is encouraged in this class, but must follow these guidelines.
Do not search for the solutions to the assignment problems in external sources. As described above: the point of the assignments is to learn the material, and you will be penalizing yourself if you try to shortcut this process.
However, you are allowed to look at sources outside of the official course material in order to understand the material better. In many situations, reading different presentations of the same material can be very helpful in understanding it better. Occasionally, you may find the solution to an assignment problem while reading one of these external sources. When that happens, just be honest: give a proper citation for the source of the solution in your acknowledgments and write the solution on your own (using your own words and, obviously, without the found solution in front of you). You will not be penalized for a solution found in another source that is cited properly and written by yourself, but failure to cite the source properly is plagiarism.
In these assignments, it is not enough to find the solution to a problem: you must also be able to clearly and effectively communicate it. You should strive to find a concise, clear, and logically sound way to present all your solutions. You should also make sure that the assignment is easy to read. If your handwriting is bad, you should consider typesetting the solutions. And if you have some difficulty writing in English, you should contact the University's Writing Centre; they have many programs that may help you.
The final grades for the class will be determined by the scores on the assignments, the midterm, and the final exam, according to the following percentages:
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. See http://uwaterloo.ca/academic-integrity for more information.
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.
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, TA, 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, see the Guidelines for the Assessment of Penalties.
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 are grounds. A student who believes he/she has grounds for an appeal should refer to Policy 72 (Student Appeals).
AccessAbility Services (formerly the Office for Persons with Disabilities), located in Needles Hall, Room 1132, 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.