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. Last year this course was online only, so I'm happy to be back in a classroom. You should attend in person, although I will continue to share and record meetings via zoom (see our home page for the zoom link).

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, Jiahao Zhao (jiahao.zhao@emory.edu). He will mostly do grading, but he should also have a weekly office hour, to be announced.

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 25% of your grade. We will have six written homework assignments (hw1, hw2, ...), altogether worth 45% 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 85 (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. You will also be asked to prepare a short writeup and video presentation on an advanced topic (which we will negotiate), and for you this will replace the last written assignment (hw6, but it cannot be dropped). Your final exam may be slightly different. The two courses are otherwise identical.

Schedule: we have 28 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 (we could get delayed).

Late work: each written assignment has a late penalty of 10% per day (computed fractionally), up to a maximum of 5 days. After that, you get no credit. I will grant each student up to three 1-day extensions on assignments, which you may use when you wish. Additional extensions may be available for documented situations (illness, conferences, accommodations, etc).

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.