CS Theory, COMS 3261, SPRING 2024, Josh Alman

CS Theory

COMS 3261, SPRING 2024

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: Mondays and Wednesdays, 2:40 – 3:55 PM
  • Classroom: 417 International Affairs Building
  • TAs:
    • Alice Chen (yc3877@columbia.edu),
    • Daniel Cheng (dwc2119@columbia.edu),
    • Fernando Notari (fc2672@columbia.edu),
    • Helen Chu (hc2932@columbia.edu),
    • Jeannie Ren (jr3766@columbia.edu),
    • Walter McKelvie (w.mckelvie@columbia.edu),
    • William Pires (head TA; wp2294@columbia.edu)

Office Hours: The calendar below has the time and location of each office hour. Before going to office hours, please check the calendar for any last minute changes.


Different Sections: This is section 1 of Columbia COMS 3261 for spring 2024. Another section is being taught this semester by Prof. Mihalis Yannakakis. These are two separate classes, which will cover different material, and which will have different assignments and exams.

Textbook: Readings and homeworks will be assigned from Introduction to the Theory of Computation by Michael Sipser. Either the Second or Third Edition is acceptable. We will follow the book in class, but with some departures. Students are responsible for all material taught in class.

Prerequisite: Discrete Math (COMS 3203) is a very important 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.

Assignments and Grading: The final grade will be based on Homework (30%) and two exams (35% each). The exams will be in class on March 6 and April 29.

There will be six homeworks, roughly one every other week. They will be released on Mondays and due Wednesdays 9 days later. Late homeworks will not be accepted so that we can quickly provide solutions and feedback. To account for this, we will drop your lowest homework grade when calculating your final grade.

That said, we will make every effort to provide accomodations for emergencies (such as serious medical or family emergencies). Please provide all necessary documentation to your advising dean, and have the dean contact me.

For any homework or exam problem, you are welcome to write "I don't know" instead of submitting an answer, and we will give you 20% of the credit. (Clarification on Feb 3: This does not apply to bonus questions, sorry!)

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, and you must list the references you used. You may not consult any other materials, including solved homework problems for this or any other course.

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.

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.

Regrade Requests: You may submit regrade requests for assignments 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. 

Materials

Lecture notes, homework assignments and solutions, 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 posted on Monday, Jan 22 and due Wednesday, Jan 31.
  • Homework 2 posted on Monday, Feb 5 and due Wednesday, Feb 14.
  • Homework 3 posted on Monday, Feb 19 and due Wednesday, Feb 28. (Problem 2 updated on Feb 20.)
  • Homework 4 posted on Monday, Mar 18 and due Wednesday, Mar 27.
  • Homework 5 posted on Monday, Apr 1 and due Wednesday, Apr 10.
  • Homework 6 posted on Monday, Apr 15 and due Wednesday, Apr 24.

Lecture Summaries: Here are very brief summaries of each lecture and corresponding readings. The readings refer to sections of the Sipser textbook unless noted otherwise. Lecture recordings can be found in CourseWorks.

  • Jan 17: Intro to the course, logistics, motivation. Alphabets, strings, and languages. Reading: chapter 0, particularly chapter 0.1 and the "Strings and Languages" part of chapter 0.2.
  • Jan 22: Review of 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 24: More DFA practice. Constructing a DFA for a given language. Formal definition of a DFA. Reading: second half of chapter 1.1.
  • Jan 29: Define regular languages. Closure properties of regular languages: complement and union. Reading: End of chapter 1.1 (the part called "The Regular Operations"). Notes about proving that the set of regular languages is closed under union at different levels of formality.
  • Jan 31: Proving a language is not regular using the pumping lemma. Reading: Chapter 1.4.
  • Feb 5: Nondeterministic Finite Automata, and equivalence with DFAs. Reading: Chapter 1.2.
  • Feb 7: Example conversion from NFA to DFA. NFAs and closure properties. Regular Expressions. Reading: Chapter 1.2 and start of Chapter 1.3.
  • Feb 12: Regular Expressions, and proof sketch that they can express all regular languages. Reading: Chapter 1.3.
  • Feb 14: Streaming algorithms. A language has a constant-space streaming algorithm if and only if it is regular. Reading: lecture notes.
  • Feb 19: Big-O notation review. Streaming algorithm space lower bounds. Reading: lecture notes.
  • Feb 21: Communication complexity. Reading: lecture notes.
  • Feb 26: Lower Bounds Review. Reading: lecture notes.
  • Feb 28: Finish communication review and more complicated streaming lower bound.
  • March 4: CFGs; Exam Review. Reading: Chapter 2.1.
  • March 6: Exam.
  • March 18: Turing Machines. Reading: Chapter 3.1.
  • March 20: More Turing Machines and Variants. Reading: Chapter 3.1 and 3.2.
  • March 25: Algorithms and Turing Machines. Reading: Chapter 3.3.
  • March 27: Undecidability of A_TM. Reading: Chapter 4.2.
  • April 1: Mapping Reductions, and proving that other languages are undecidable or unrecognizable. Reading: Chapter 5.3.
  • April 3: More examples of undecidability, including the Post Correspondence Problem. Reading: Chapter 5.2.
  • April 8: Time complexity and the class P. Reading: Chapter 7.1 and 7.2.
  • April 10: Polynomial-time Verifiers and the class NP. Reading: Chapter 7.3.
  • April 15: (plan) NP-completeness. Reading: Chapter 7.4.
  • April 17: (plan) NP-completeness continued. Reading: Chapter 7.4 and 7.5.
  • April 22: (plan) Exam Review.
  • April 24: (plan) Epilogue.
  • April 29: Exam.