CS Theory, COMS 3261, SPRING 2025, Josh Alman

CS Theory

COMS 3261, SPRING 2025

Description

This course is an introduction to the theory of computation. We will aim to answer questions like: What is computation? What is a model of computation, and what are desirable properties of such a model? What computational problems can be solved efficiently? What problems can be solved at all? For some of these questions, we will give clean and precise mathematical answers. Meanwhile, some of the other questions will lead us to major open problems in computer science and mathematics!

This course is highly mathematical and abstract. There will be no programming assignments, and homework problems will frequently involve mathematically proving interesting facts.

Topics will include: Automata, Turing machines, and other computational models; Computability theory (such as the undecidability of the halting problem); Complexity theory (such as the P vs. NP problem).

General Information

  • Instructor: Josh Alman
  • Time: Tuesdays and Thursdays; 1:10-2:25PM (section 1), 2:40-3:55PM (section 2)
  • Classroom: 833 Mudd Building
  • TAs:
    • TBA

Different Sections: There are two different sections of COMS 3261 for spring 2025. These two sections will share the same homeworks, office hours, gradescope and edstem pages.

Office Hours: Once the class begins, we will post a calendar here with the time and location of each office hour. We plan to have many available throughout each week.

EdStem: Our course staff will also monitor the course edstem, and we encourage you to ask questions there, especially if you think they may be of interest to other students in the class. If you ask any questions about solutions or other personal information, please ask them privately to the course staff. See the CourseWorks page for a link to the edstem once the semester starts.

Lectures: Lectures are typically not recorded, but we will post readings and notes corresponding to the lectures. It is acceptable to attend the lectures of the other section, except for when we have in-class exams.

Textbook: Readings and exercises will be assigned from Introduction to the Theory of Computation by Michael Sipser. Either the Second or Third Edition is acceptable. That said, we will cover some material which does not appear in the textbook, and students are responsible for all material taught in class.

Prerequisite: Discrete Math (COMS 3203) is the prerequisite for this class. See Chapter 0 of the Sipser textbook (linked here if you don't have the book yet) and Tim Randolph's "homework 0" (linked here, and solutions) to review concepts from discrete math which we will assume familiarity with. In particular, we will assume you are comfortable with reading and writing mathematical proofs.

This is a very important prerequisite which we will rely on throughout the entire class. If you have difficulty with any of the above, and have not yet completed COMS 3203, you should drop this class and take COMS 3203 first. If you have taken COMS 3203 and have difficulty, come speak to the professor and teaching staff during office hours, to deal with any issues early on.

Assignments and Grading

The final grade will be based on six homeworks and two exams.

Many homework problems will be simpler exercises aimed at practicing and reinforcing what we learned in class, but homeworks will also include some challenging problems which will require creative problem solving and applying the concepts from class in new ways. By contrast, the exams are aimed at testing a solid understanding of the material from class, and not problem-solving skill; they will primarily have types of problems that students should be familiar with from class and homeworks. In other words: the homeworks are intended to be more challenging than the exams.

Exam Logistics: The exams will be in class on March 13 and May 1. You must attend your assigned section's lecture time on the exam days. Before each exam, we will release a practice exam with a similar format to the real exam.

The second exam is not "cumulative", and will primarily test material from the second half of the class. That said, the material in this class naturally builds on itself, and topics we will learn in the second half of class will depend on concepts from the first half of class.

Grading: The assignments will be weighted in whichever of the following two ways results in a better score for each student:

  • Homework (24%), First Exam (38%), Second Exam (38%)
  • Homework (24%), First Exam (26%), Second Exam (50%)

This means that a strong performance on the second exam can substantially mitigate a weaker performance on the first exam.

Homework Content: There will be six homeworks, roughly one every other week. The tentative homework schedule is in the materials section below. Each homework will have three kinds of problems:

  • Exercises: These will be problems, often from the textbook, that we recommend you solve for practice at understanding the material. We will not grade these problems, and you should not turn in your solutions to them. Their solutions can often be found in the textbook at the end of the chapter.
  • Problems: These are the main problems you should solve and turn in solutions for. Your homework grade will be entirely based on your scores on these problems.
  • BONUS Problems: These are extra, more difficult problems for students who would like an additional challenge. You should turn in solutions to these problems if you would like, and we will grade them, but we do not expect most students to attempt most bonus problems. At the end of the semester, we will ignore bonus problems when determining final grade cutoffs, and then add in bonus points to your final score afterwards. In other words, everyone's final grades will be calculated without considering bonus points at all, but then we'll check whether the bonus points bump you up.

Partial Credit: Unless instructed otherewise, we encourage you to explain how you got to your answer on all homework and exam problems, and not just state your final answer. We will give partial credit to answers which are incorrect but make substantial progress toward a correct response, but we can only give you partial credit if you explain your reasoning. That said, we will typically not give partial credit for bonus problems on the homework, other than for solutions which are very close to fully correct. Some other problems (like true/false problems on exams) will also not have partial credit available.

Homework Grading and Late Submissions:  We plan to grade each homework very shortly after it is due in order to quickly provide solutions and feedback. Since the material in this class builds on itself throughout the semester, we feel it is important to give quick feedback.

The first time a student submits a homework assignment late, we will accept it without penalty as long as it is submitted at most 10 hours after the deadline. We will not accept a second or subsequent late homework submission from a student, and we will not accept any submissions more than 10 hours after the deadline.

That said, we will make every effort to provide accommodations for emergencies (such as serious medical or family emergencies). If such a scenario arises, please provide all necessary documentation to your advising dean, and have the dean contact Prof. Alman to discuss appropriate accommodations. In particular, please send medical notes or other similar documentation to your advising dean and not to Prof. Alman.

Homework Submission and Collaboration: Collaboration with other students in the class is allowed (but not required) on homeworks. However, you must write up your solutions entirely by yourself, and list the names of everyone you collaborated with. In particular, you should not write up solutions with other students or look at written solutions by other students.

You may consult lecture notes, videos, and textbooks from this or other classes while doing homeworks, as long as you list the references used at the end of your homework submission. You may not consult any other materials, including homework problem solutions for this or any other course.

It is also prohibited to use generative AI tools like ChatGPT while working on homeworks. (Even if it were not prohibited, these tools typically give incorrect and confusing solutions to the types of problems we will see in this class. In fact, in this class, we will give a mathematical explanation for this phenomenon!)

Homework Submissions Logistics: Homework should be submitted through the Gradescope website. We will use anonymous grading. Please do not put your name or other identifying information on any page of your submission that will be graded. We will ask you to list your collaborators and other materials used on a separate page, not linked to any problem. Please also be sure to follow other formatting rules listed on the homework assignment, such as writing each solution on a separate page.

We recommend that you typeset your homework (using LaTeX, for instance), but we will also accept scanned, legibly handwritten homework. We will not spend much effort trying to decipher handwriting that we have trouble reading. If we cannot read your writing, we will give you a temporary score of 0 and ask that you submit a regrade request where you type out what you wrote for us to grade.

Regrade Requests: You may submit regrade requests for homeworks or exams through Gradescope. Regrade requests must be submitted within one week of the grade being released. Include with your regrade request a clear and detailed argument for your request. When we are regrading questions, we reserve the right to regrade the entire assignment or exam, which could result in the overall score being raised, lowered, or remaining unchanged.

Academic Honesty: In addition to all the above, students are assumed to be aware of the CS department's academic honesty policy and must abide by it. We will follow the policies of the department and university in case of any suspected academic dishonesty.

Materials

Lecture notes, homework assignments, and other materials will be posted here! We will post notes about what was covered and the corresponding reading after each lecture.

Homeworks: 

  • Homework 1 will tentatively be posted Jan 28 and due Feb 6 at noon
  • Homework 2 will tentatively be posted Feb 11 and due Feb 20 at noon
  • Homework 3 will tentatively be posted Feb 25 and due Mar 6 at noon
  • Homework 4 will tentatively be posted Mar 25 and due Apr 3 at noon
  • Homework 5 will tentatively be posted Apr 8 and due Apr 17 at noon
  • Homework 6 will tentatively be posted Apr 17 and due Apr 24 at noon (This will be a short homework.)

Lecture Summaries: Here is the tentative plan for each lecture and corresponding readings. We will update these summaries as we progress through the semester. The readings refer to sections of the Sipser textbook unless noted otherwise.

  • Jan 21: Intro to the course, logistics, motivation. Reading: chapter 0, particularly chapter 0.1 and the "Strings and Languages" part of chapter 0.2.
  • Jan 23: Alphabets, strings, and languages. Transition diagrams for DFAs. The language recognized by a DFA. Practice determining the language of a DFA. Reading: first half of chapter 1.1.
  • Jan 28: More DFA practice. Constructing a DFA for a given language. Formal definition of a DFA. Reading: second half of chapter 1.1.
  • Jan 30: Define regular languages. Closure properties of regular languages: complement and union. Reading: End of chapter 1.1 (the part called "The Regular Operations").
  • Feb 4: Proving a language is not regular using the pumping lemma. Reading: Chapter 1.4.
  • Feb 6: Nondeterministic Finite Automata, examples and definition. Reading: first half of Chapter 1.2.
  • Feb 11: Equivalence between NFAs and DFAs. NFAs and closure properties. Reading: second half of Chapter 1.2
  • Feb 13: Regular Expressions, and proof sketch that they can express all regular languages. Reading: Chapter 1.3.
  • Feb 18: Big-O Notation. Reading: Part of Section 7.1 on Big-O Notation. 
  • Feb 20: Streaming algorithms. A language has a constant-space streaming algorithm if and only if it is regular. Reading: Notes to be posted.
  • Feb 25: Streaming algorithm space lower bounds. Reading: Notes to be posted.
  • Feb 27: Communication Complexity, and example protocols. Reading: Notes to be posted.
  • March 4: Communication lower bounds. Reading: Notes to be posted.
  • March 6: A brief tour of context-free languages. Reading: Chapter 2.
  • March 11: Turing Machines. Reading: Chapter 3.1
  • March 13: First Exam, in class. You must attend your own section's lecture time on this day. All material before context-free languages will be covered. Context-free languages and Turing machines will not appear.
  • March 25: More Turing Machines and Variants. Reading: Chapter 3.1 and 3.2.
  • March 27: Algorithms and Turing Machines. Reading: Chapter 3.3.
  • April 1: Undecidability of A_TM. Reading: Chapter 4.2.
  • April 3: Mapping Reductions, and proving that other languages are undecidable or unrecognizable. Reading: Chapter 5.3.
  • April 8: More examples of undecidability, including the Post Correspondence Problem. Reading: Chapter 5.2.
  • April 10: Time complexity and the class P. Reading: Chapter 7.1 and 7.2.
  • April 15: Polynomial-time Verifiers and the class NP. Reading: Chapter 7.3. 
  • April 17: NP-completeness. Reading: Chapter 7.4. 
  • April 22: NP-completeness continued. Reading: Chapter 7.4 and 7.5.
  • April 24: P vs NP and connections with other topics. Reading: Chapter 7.
  • April 29: Epilogue.
  • May 1: Second Exam, in class. You must attend your own section's lecture time on this day. All material starting from Turing machines (March 11 lecture) will be covered