Welcome to CS424/CS524, Theory of Computing!

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 will attempt to share and record our meetings via zoom (see our home page for the zoom link). 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 also have a TA, Yuzhang Xie, who will do much of the grading.

Textbook: we will use Sipser's Introduction to the Theory of Computation (3rd edition). We cover Chapters 1 through 8 (roughly). 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.

Graded Work: we will have one midterm exam (an online Canvas quiz) worth 15% of your grade, and a final exam (on paper) worth 30% of your grade. We will have six written homework assignments (hw1, hw2, ...), altogether worth 40% of your grade; we will drop your lowest mark among these. The remaining 15% is participation, which includes things like review discussions. Each individual exam and homework assignment is curved, if necessary, so that the median non-zero mark is at least an 84 (B).

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. 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. Your final exam may be slightly different. The two courses are otherwise identical.

Schedule: we have 27 regular meetings, so about 14 weeks to cover about 8 chapters. For a day-by-day plan of lectures, assignments, and exams, see the pages and modules. Note our plans are subject to change (i.e, we could get delayed).

Late work: for the late policy on written assignments, see Grading of Written Assignments. "Participation" items should include a late penalty in their description (like: "-1 per date late"). I may grant extensions for some documented situations (illness, conferences, team travel, accommodations, etc), please request extensions well in advance if possible. You cannot be late on exams.

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.