CPSC 421 (Introduction to Theory of Computing)

Description

Introductory course on automata theory, computability theory, and complexity theory.

Textbook

· M. Sipser, Introduction to the Theory of Computation. 1^st edition is pretty old, but 2^nd and 3^rd edition are almost equivalent for our purposes. The 2^nd edition is available on Amazon used for $21.

· Frequently Asked Question: Is the textbook mandatory for this course?

o Answer: Realistically, I don’t have any way to enforce whether you buy the textbook or not, so declaring it to be “mandatory” has little consequence. I think you will strongly benefit from having a copy of the textbook because its proofs are more detailed than the lectures, it is extremely well written, it discusses a lot of context of the course material, and it has more examples than we will have time to cover. It also has useful practice problems. The CS reading room has several physical copies.

· Frequently Asked Question: Why is the textbook so expensive?

o Short answer: The principal-agent problem?

o Long answer: Listen to the podcast “Why Textbook Prices Keep Climbing”. In particular, keep in mind Mankiw’s quote “The biggest expenditure for students is not the expenditure of money, but it's the expenditure of their time.”

Grading Scheme

· 25%: Assignments

· 25%: Midterm

· 50%: Final exam

There is no additional requirement to pass the exams.

Assignment Guidelines

Collaboration: You can work alone or in a group of two. Each group should make a single submission per assignment. Collaboration with others is limited to discussion and brainstorming. Each group must write their own independent solution, using their own words. Acknowledge all collaborators or sources of assistance in your submission, although you need only name CPSC 421 course staff, handouts, and textbooks if you quote or adapt directly from them.

Formatting: We require that assignments be submitted using LaTeX. We will make the .tex version of the assignment available, to make it easier for you to prepare your solutions using LaTeX. Submissions that are not typeset in Latex will incur a severe penalty. Their grade will be multiplied by 0.5.

Submission: Submit your assignments on Gradescope by 11:59:00pm. You can submit early and resubmit as often as you want up to the deadline. We strongly encourage you to submit something a few days in advance of the first assignment, to make sure that things are working properly.

After uploading to Gradescope, link each question with all the pages of your pdf containing your solution. Add CSID's of group members on GradeScope after one student has made the initial submission. As a secondary failsafe, please clearly write the CSIDs of all group members on the first page of each submission. Do not include your names or any other identifying information on your assignments.

Late submissions: Late homework submissions will not be accepted, due to the very short turnaround time required in grading.

Prerequisites

The most important prerequisite for this course is the ability to write a logical proof, especially an inductive proof. I also expect you to be familiar with the following concepts:

• Basic programming notation, basic algorithms
• Asymptotic analysis, Big-O notation
• Basic discrete math: sets, graphs, strings, finite fields
• Basic discrete probability: expectation, conditioning, etc.

To review these topics, see the first chapter of the textbook, or Lehman, Leighton and Meyer Ch 1-5, 11, 13.

Regrading Requests

We do our best to grade all submissions fairly and consistently. Because graders occasionally make mistakes, we welcome regrade requests that help us correct such mistakes and ensure fairness. You have one week from the time that the grades are posted to submit a regrade request on Gradescope. Please be respectful and help us ensure that time spent on regrades is productive by following these guidelines.

• Prior to making a regrade request, make sure you understand the solution to the problem, and read any comments provided on Gradescope or Piazza about how the problem was graded. If you don't understand what's missing from your answer, come see one of us during office hours before submitting a regrade request.
• Explain clearly and specifically why you believe your mark is inappropriate, referring to your solution, and the rubric. Good examples: "I lost a point for not initializing my table entries, but I initialize them in line 6." Or, "My solution is quite different from the one in the sample solution, but I'm confident that my approach also works for the following reason..."
• Don't submit a request because you think the rubric is unfair, or if you disagree with a judgment call of the grader. A bad example that disputes the rubric is: "I lost a mark for not justifying my answer, but I didn't think I needed to justify my answer, and I don't feel I should be penalized." A bad example that disputes a judgment is: "I should get 'minor errors (-0.5 points)' instead of 'significant errors (-2 points)'." An example that is not sufficiently specific is: "My friend gave basically the same answer and got a higher grade."

The person who graded the question will review your request, possibly with input from an instructor or other TAs. The decision of your TA or instructor is final. It may either increase or decrease your mark. Submitting several poorly-explained regrade requests may result in a penalty.

Equity, Inclusion & Wellness

See https://www.cs.ubc.ca/students/undergrad/resources/equity-inclusion-wellness

Academic Disconduct

See https://www.cs.ubc.ca/students/undergrad/resources/academic-integrity