Welcome to CS-424 (and CS-524), Theory of Computing! See our home page for the course schedule, room, and zoom link.

Overview: In this course we take an abstract view of computation. We study models of computation, and their ability to solve fundamental problems.  We will work on how to write and talk about such problems and models.  The material is mathematical.  Much of your work will be written, including proofs.  You need to be comfortable talking about algorithms and computation, in a high level way.  

We will use Canvas for announcements, discussions, assignments, and grading. I do not take attendance, but I encourage you to attend in person when possible.

Staff: your instructor (writing this!) is Professor Michelangelo Grigni.  You may reach me at mgrigni@emory.edu, or at my zoom/office hours. We should have a TA, to be announced.

Textbook: we will use Sipser's Introduction to the Theory of Computation (3rd US edition). We cover roughly Chapters 1 through 9. We follow the book closely, so get access to a copy (print, ebook, or pdf is fine). You should read the book, preferably ahead of lectures. I think it is well-written, I hope you enjoy it! Beware that the page numbering (and some problem numbering) is different in the "international edition", so try to find the US edition. Here is a check: page 300 should start with "Theorem 7.27, SAT∈NP iff P=NP".

Graded Work: We will have six written homework assignments (hw1, hw2, ...), altogether worth 40% of your grade; we will drop your lowest mark among these. We will have one midterm exam (an online Canvas quiz) worth 15% of your grade, and a final exam (in person, on paper) worth 25% of your grade. The remaining 20% is participation items, which are mostly review discussions; we will drop your lowest mark among these. Each individual exam and homework assignment is curved, if necessary, so that the median non-zero mark is at least an 83 (B). We rarely need the curve on homeworks, but exams can be harder.

Exams will be relatively fact-based and non-creative, checking the facts of the course. Written homeworks will be more creative, with some challenging problems that require some thought. You should submit something for each problem, even if you cannot finish it. Participation items will be relatively easy.

CS-524: Compared to CS-424, students in CS-524 may be asked to do a bit more reading, and to solve somewhat harder problems. The exams may also be slightly different. The two courses are otherwise identical.

Schedule: we have 28 regular meetings to cover about 9 chapters. For a day-by-day plan of lectures, assignments, and exams, see the pages and modules (or the Canvas calendar). Our plans could change, but any changes will be announced.

Late work: for the late policy on written assignments, see Grading of Written Assignments. For the late policy on readings, see Grading of Readings. Other items should include a late penalty in their description. I may grant extensions for documented situations (illness, conferences, team travel, accommodations, etc), please request extensions well in advance if possible. 

Policies: it is your responsibility to know what is covered in class meetings, to review the course materials, and to attempt all assigned work. Your work for this class is governed by the College Honor Code (or LGS Honor Code).  The following kind of collaboration is allowed: interpreting the statement of a problem, understanding software tools, or reviewing the course materials. But unless instructed otherwise, you should not seek or share help on assignments or exams. Even when collaboration is allowed, your submitted work should still be your own; your wording and diagrams should not look like a copy of somebody else. If you are in doubt about what is allowed, just ask.

Accessibility: The Department of Accessibility Services (DAS) works with students who have disabilities. In order to request accommodations, you first register with DAS, and then submit their letter to me. For more information, contact me or accessibility@emory.edu.