This undergraduate course provides a broad introduction to the mathematical foundations of computer science. We will examine basic computational models, especially Turing machines. The goal is to understand what problems can or cannot be solved in these models.
The textbook for the course is Introduction to Theory of Computation by Michael Sipser. (Any edition is fine.) This book covers most of the topics in the course. Further reading, especially for later topics: Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak. (For this book, drafts of all chapters are available here.)
The formal course prerequisite is CS 2800 (Discrete Structures). To follow the course, you will need basic mathematical maturity (the ability to understand and develop mathematical proofs). If you haven’t taken CS 2800 before, please contact the instructor.
Grading is based on weekly homework, three in-class exams, and participation (in class, office hours, and piazza). Grading scheme (tentative):
- Homework: 45
- Exams: 45 (= 3 × 15)
- Participation: 10
Participation is an important part of the course. Besides class and office hours, a good way to participate is to ask and answer questions on piazza about course material. Piazza is also the preferred way to contact the instructors about any course-related issues.
Homework is an important part of the course. We will have weekly homework assignments.
Your homework submissions need to be typeset (hand-drawn figures are OK). The idea is that you first develop your solutions on paper and then type up their final form in a concise way. See typesetting resources for a list of typesetting software and references.
You have eight late days. Late submission are graded only if you use your late days (up to two per homework). If you are unable to submit your homework because of extenuating circumstances (medical or family emergency), contact the instructor beforehand.
If you clearly indicate gaps in your homework solutions, you will get more partial credit. For example, if you write that you don’t know the solution of a problem, you will get 20% of the points, whereas you will not earn any points if you submit a solution that is completely wrong.
You can collaborate in (disjoint) groups of up to three students. You need to submit homework individually (written by yourself, in your own words). Your submission should acknowledge all members of your group. Resources beyond course material and group discussions are not admissible. However, if you do end up using other resources, you absolutely need to reference them (see academic integrity).
List of topics covered in this course (tentative):
- Finite Automata
- non-determinism, regular expressions
- state minimization, pumping lemma
- Computability and Logic
- Gödel’s completeness and incompleteness theorems
- Church–Turing thesis, universality
- explicit undecidable problems, diagonalization
- time and space bounded computation
- P vs NP, NP-completeness, reductions
- hierarchy theorems, relativization
- Boolean circuits
- probabilistic and quantum computation
- cryptography and machine learning
From the code of academic integrity:
Absolute integrity is expected of every Cornell student in all academic undertakings. Integrity entails a firm adherence to a set of values, and the values most essential to an academic community are grounded on the concept of honesty with respect to the intellectual efforts of oneself and others. Academic integrity is expected not only in formal coursework situations, but in all University relationships and interactions connected to the educational process, including the use of University resources. […]
A Cornell student’s submission of work for academic credit indicates that the work is the student’s own. All outside assistance should be acknowledged, and the student’s academic position truthfully reported at all times. In addition, Cornell students have a right to expect academic integrity from each of their peers.