CSC236 Introduction to the Theory of Computation

Summer 2024

Syllabus

Here is a one-page term schedule that gives a visual overview of the entire term.

Date Topic Tutorial Assessment
May 6 - May 12 W1: Introduction, Review, and Induction (complete) No Tutorial This Week A1 [Template, Solution + Rubric] (Due: May 20)
May 13 - May 19 W2: Induction and Counting (complete) T1: Well Ordering
May 20 - May 26 W3: Combinatorics (complete) T2: Generating Functions A2 [Template, Solution + Rubric] (Due: June 6)
May 27 - June 2 W4: Graph Theory (complete) T3: Euler Circuit
June 3 - June 9 W5: Correctness of Algorithms (complete) T4: Proof-of-correctness practice A3 [Template, Solution + Rubric] (Due: June 24)
June 10 - June 16 W6: Recursive Algorithms (complete) T5: Recursive algorithm practice
June 17 - June 23 Midterm 1 [Solutions] No Tutorial This Week
June 24 - June 30 Reading Week No Class No Tutorial This Week A4 [Template, Solution + Rubric] (Due: July 11)
July 1 - July 7 W7: Correctness of Recursive Algorithms and the Master Method (complete) T6: Master Method practice
July 8 - July 14 W8: Introduction to Formal Languages (complete) T7: DFA practice A5 [Template, Solution + Rubric] (Due: July 29)
July 15 - July 21 Midterm 2 [Solutions] No Tutorial This Week
July 22 - July 28 W9: Equivalence of DFA, NFA, and Regex (complete) T8: Regular Expressions
July 29 - Aug 4 W10: Pumping Lemma and Limitations of Finite Automatons (complete) T9: Limitations A6 [Template, Solution + Rubric] (Due: August 8)
Aug 5 - Aug 11 W11: Review and Student's Choice (complete) No Tutorial This Week

Course Description

This course is an introduction to abstraction and rigour in computer science. The topics we will cover are: induction and its applications to combinatorics and graph theory, proof of correctness of algorithms, and finite automaton. From prior courses we expect you to be able to use asymptotic notation and be familiar with simple induction.

Prequisites: either CSC111H1 (minimum grade of 60) or (CSC148H1 (minimum grade of 60) and CSC165H1)
Exclusions: CSC240H1, CSC236H5, CSCB36H3

Learning Outcomes

In this course, you will learn…

The domains we study in this course include:

Marking Scheme

Assignments

Each assignment consists of two ungraded warm-up questions, two graded questions, and a list of relevant questions from the primary and secondary textbooks. The ungraded questions may appear on the Midterm or Final so it is a good idea to be able to solve them. Start the assignments early! Each assignment will also have a peer review component worth a portion of the total marks (typically 5 out of 25 marks). You and your group members will be given a rubric, some sample graded solutions, and are tasked with grading 5~10 other submissions. The TA will then grade the assignment and the accuracy of your proposed grade (by standard deviation) to the TA's grade will be your score. In order to ensure that the peer review is unbiased please do NOT include any identifying marks on your submission e.g. name, student ID, UTORID etc. You can submit an assignment up to 3 days late (72 hours). Each day will result in a 10% reduction. After the 3rd day the solutions will be released so no more submission will be accepted.

Submission instructions

Midterms and the Final

If you miss a midterm for approved reasons, we will meet with you for an oral exam (30~60 minutes) to determine if you are caught up with the course material. If so, we will move the weight of the component to the final. If not, you will get a zero for that component. If you miss more than one midterm, we will require that you to make an appointment with your College Registrar to put in place a concrete plan for the rest of the term, before we approve any exception. This ensures that you are realistic about your ability to succeed in the course and that you have thought about how you will manage the risk. We will require confirmation from your College Registrar that you have met and discussed this with them.

In order to receive special consideration, you must fill out a Request for Special Consideration Form. Complete and submit the form online as soon as you can, together with supporting documentation. These include Absence Declaration (via ACORN), or the University’s Verification of Student Illness or Injury (VOI) form, or letters from your College Registrar or Accessibility Services. NOTE: Absence Declaration can be used at most ONCE PER TERM, and for a maximum of seven consecutive days (this is a new policy). For more information on each type of documentation, including when and how to use it, please read all the details carefully on the new Student Absences page from the Faculty of Arts & Science.

IMPORTANT: If you know that you will NOT be able to write a midterm, just submit the request form as soon as you are able (and have obtained appropriate documentation). It is NOT necessary to send email for “simple” requests due to illness / injury or personal / family emergencies — just the form is sufficient. However, if your situation is particularly unusual or complex, please contact us (using the email listed at the top) to discuss the details as soon as you can (even before you have obtained documentation).

If you face a situation that is particularly disruptive (especially if it is likely to affect more than one course), please also contact your College Registrar — they are best equipped to provide you with general advice and support that goes beyond a single course. They can also help you document your situation and contact each of your course instructors on your behalf, to simplify the process of requesting accommodations. Keep in mind that course instructors cannot grant Special Consideration for the Final! If you are unable to write the final exam, please contact your College Registrar for the next steps — the process is explained in more detail on the Sidney Smith Commons.

You are expected to write every test. The policies described above are NOT meant for you to simply choose to “skip a test”. Rather, it is meant for emergencies: situations where you are truly unable to write the test with everyone else (not just when it is inconvenient).

What to expect for tests (in general)

Midterms will contain 4–5 questions, at least one of which is meant to be easy (a more-or-less direct application of course material), and at least one of which is meant to be somewhat challenging (require some creativity in applying the course material). For each part of a question in the long-answers portion of both the midterms and final, you can put "I don't know" to get 20% of the total marks for the question (long answers only NOT MULTIPLE CHOICE OR SHORT ANSWER).

How to Prepare

Review the course materials: lecture slides, quizzes, assignments. Make sure you understand how to solve them without looking and then compare your answers against sample solutions (if available). You can also read this guide to test-taking.

For the final, you can try questions from previous years’ finals. For maximum benefit, we strongly suggest the following approach: try these questions only after you have finished reviewing the rest of the materials from this term; time yourself to get the benefit of a real “test experience”, as a way to verify not only your understanding, but also your ability to answer questions quickly (this will matter for the actual tests); and finally, don’t look at the solutions until you have finished working on the questions as if it were a real test.

Make good use of the Sidney Smith Commons’ Exam Toolkit. This contains many general resources to help you prepare for term tests and the final exams, including sections on “what to expect”, “how to study”, and “strategies”.

Remark Requests

If you believe there was an error in the marking of your work — or if you just have questions about how your work was marked — you may request that it be remarked. Please complete and submit a Remark Request Form within one week of when the graded item was returned. Please note that when we receive a remark request, we may regrade the entire submission. Your mark may go up or down as a result of the remark. This is not meant to discourage you from submitting remarking requests! Just to acknowledge the reality that errors can be made in both directions in the initial marking.


Accessibility

The University of Toronto is committed to accessibility. If you require accommodations for an ongoing disability or an acute issue such as an injury, you should register with Accessibility Services (AS). The process of accommodation is both confidential and private. AS provides the information necessary to implement an accommodation and no more, e.g., what is listed in a Letter of Accommodation. Your instructors and other university staff will not reveal that you are registered with AS. Please note that the three day extension is a HARD DEADLINE. If you generally need more time, please reach out to us (through the course email) or get your AS representative to reach out to us and we can work out something specifically for you (e.g. give you access to an assignment a few days early). Please do this at least A WEEK before an assignment is due.

Students who require accommodations for term tests (or the final exam) must register with Accommodated Testing Services (ATS). We will only be providing test accommodations sent to us through that official channel. This helps to guarantee that accommodations are provided in a fair and consistent manner for everyone.

Creating a Positive Learning Environment

We are committed to creating a respectful learning environment in computer science courses for all students and expect that you will adhere to the University of Toronto’s Code of Student Conduct. Please be mindful of how your behaviour influences the atmosphere in our learning community, not just in classes, but also in computer labs, in online forums, and anywhere that you interact with other students and members of the department.


Academic Integrity

All work you submit must be your own. It is an academic offense to copy the work of someone else — even if the other person is not a student — unless you explicitly and clearly attribute the work to its original source. This includes words, sentences, entire documents, and even ideas. Whether you copy or let someone else copy, it is an offense. Academic offenses are taken very seriously and can have correspondingly serious consequences.

At the same time, we want you to benefit from working with other students. For this course, you must write up your own individual submission to every problem set — you cannot submit the same answers as another student — but you are allowed to discuss how to solve the problems with anyone you wish. The purpose of the problem sets is to ensure that you understand how to solve the problems. Even if you did not generate a solution yourself, you can still receive useful feedback on your work.

Any collaboration on, or sharing of, term test solutions or questions is strictly forbidden!

Please take a few minutes to consult the Academic Integrity at U of T website: it contains good information and concrete strategies to help support your learning in ways that follow the principles of academic integrity, in addition to references to formal policies and procedures.

What about ChatGPT and other Generative AI tools?

In this course, you may use generative artificial intelligence (AI) tools (like ChatGPT and GitHub Copilot) as learning aids and to help complete problem sets, but you must cite the tool that you used and include a transcript of your conversation with the AI. You will NOT be permitted to use generative AI on the term tests or final exam. While some generative AI tools are currently available for free in Canada, please be warned that these tools have not been vetted by the University of Toronto and might not meet University guidelines or requirements for privacy, intellectual property, security, accessibility, and records retention. Generative AI may produce content which is incorrect or misleading, or inconsistent with the expectations of this course. They may even provide citations to sources that don’t exist — and submitting work with false citations is an academic offense. These tools may be subject to service interruptions, software modifications, and pricing changes during the semester.

Generative AI is NOT required to complete any aspect of this course, and we caution you to not rely on these tools to complete your coursework. Instead, we recommend treating generative AI as a supplementary tool only for exploration or drafting content — always remembering to cite any resource you used to generate your answers. Ultimately, you (and not any AI tool) are responsible for your own learning in this course, and for all the work you submit for credit. It is your responsibility to critically evaluate the content generated, and to regularly assess your own learning independent of generative AI tools. Overreliance on generative AI may give you a false sense of how much you’ve actually learned, which can lead to poor performance on the term tests or final exam, in later courses, or in future work or studies after graduation.


$\LaTeX$ Help

$\LaTeX$ is a standard typesetting program used in the sciences. We encourage you to learn to use it — though this is not necessary. In this section, we provide some resources to help you get started with $\LaTeX$.