Skip to main content



Under Construction    Website under construction—all information subject to change!

Course Info

Overview

An introduction to the classical theory of computing: automata theory, formal languages, and effective computability. Topics include finite-state machines, regular languages, regular expressions, grammars, context-free languages, pushdown automata, Turing machines, recursive and recursively enumerable sets, diagonalization, reductions, undecidability, Gödel's incompleteness theorem. A complete list of topics can be found on the schedule page (subject to change). As time permits, we will explore some more modern advances such as coalgebraic methods, abstract interpretation, and concurrency.

3 credits, grade or S/U.

Time & Place

TuTh 10:10–11:25am, location TBA.

Staff

  Name/Position Contact Office hours Location
Photo of Dexter Kozen Dexter Kozen
436 Gates
Instructor		 [mouse over for email]
607-592-2437 		TuTh 1:30-2:30pm
or by appt
 436 Gates
a big lambda Corey Torres
401 Gates
Admin		 [mouse over for email]
M-F 8am-4:30pm
a big lambda TBA
Teaching assistant

Prerequisites

CS 2800 or permission of instructor.

You should be familiar with graphs, trees, dags, sets, functions, relations, equivalence relations, and partial orders. The course is quite theoretical and involves proofs, so you should be comfortable with mathematical arguments, especially induction, at the level of CS 2800. In addition, familiarity with the content of CS 3110 and a course in elementary logic or algebra such as Math 3340 or Math 4810 will be helpful, but not essential.

Text

The text is available at the Cornell Store. Note that, although the text was designed for this course, there will be topics covered in lecture that are not in the text and vice versa. You are responsible for topics covered in lecture and for any assigned reading in the text.

The following are some other useful sources.

These titles are on reserve at the Engineering library.

Schedule

The schedule page lists the topics to be covered in lecture and the corresponding readings in the text, exam dates, and homework due dates. This is subject to change.

Handouts

Supplementary course material will be posted on the handouts page. Check often for new postings.

Ed

We will be using Ed as an online discussion forum. Ed allows for open discussions of all course-related questions. You are encouraged to post any questions you might have about the course material. The course staff monitor Ed closely and you will usually get a quick response. If you know the answer to a question, you are encouraged to post it.

By default, your posts are visible to the course staff and other students. You should prefer this mode so that others can benefit from your question and the answer. You can post anonymously if you wish.

You can also post privately, and only the course staff will see your question. You should use this mode if your post might reveal information about a solution to a homework problem or for communications of a sensitive nature. If you post any part of a solution publicly, it will be considered a violation of academic integrity.

Do not confuse anonymous posting with private posting. If you post privately when there is no need, we reserve the right to make your question public if we think the class will benefit.

Everyone who preregistered for the course should already be signed up. If you have never used Ed before, or if you did not preregister for the course, visit the signup page to sign yourself up.

Ed is the most effective way to communicate with the staff outside of office hours. Please avoid email if Ed will do.

All course announcements will be posted on Ed. Please check frequently for new postings.

CMSX

We will be using the CS course management system CMSX to manage course grades and assignments. We will not be using Canvas. Everyone who preregistered for the course should already be enrolled in CMSX, but if you registered late, you may be missing. Please login and check whether you exist. There will be a list of courses you are registered for, and CS 4810 or 5810 should be one of them. If not, please send your full name and Cornell netId to the course administrator so that you can be registered.

You can check your grades, submit homework, and request regrades in CMSX. Please check your grades regularly to make sure they have been properly recorded. The system also provides some grading statistics. There is a help page with instructions.

Homework

There will be weekly homework assignments consisting of 4-6 problems due at 11:59pm on the due date. Assignments and solutions will be posted in CMSX. There will be one or more extra problems, typically more difficult, on each homework assignment for the CS 5810 students. CS 4810 students may also do them for additional credit.

Late Homework  Assignments may be turned in late with a grade penalty of 5% per hour of lateness, up to the total value of the assignment.

Deadline Extensions  Each student is entitled to 72 hours of free deadline extensions during the semester. You must have a valid excuse and request the extension in advance of the deadline. You may request an extension for any multiple of 24 hours. The definition of valid excuse is very liberal and will be interpreted to include excessive workload in other classes, minor illness, job interview, or other reasons at the discretion of the staff. Extensions for major illness or emergency do not count against this entitlement. In such cases, please inform the course staff as soon as possible.

All course staff members are empowered to grant free extensions. To request a free extension, contact a member of the course staff by email and include your netId, your excuse, and the requested length of the extension.

If you are granted a free extension and manage to finish before the deadline, sorry—you cannot cancel the request. (Think for a few seconds about why it would be a bad idea to allow this.)

Submitting Homework  You should submit a typeset electronic version of your homework to CMSX in .pdf format. We recommend LaTeX for typesetting. Unfortunately we cannot accept scanned or photographed handwritten homework due to illegible script and large file sizes. LaTeX templates, including sources for all homework assignments, can be found on the handouts page.

After submitting your homework, please download it from CMSX and double-check that you submitted what you intended to submit. If you submitted the wrong file, submitted a corrupt .pdf file, neglected to include a file, or something similar, out of fairness we cannot accept your solutions later.

Collaboration  Homework assignments may be done individually or in pairs. Collaboration with a partner is encouraged. If you collaborate, one of the group members must invite the other in CMSX and the other must accept. Only one person in the group needs to submit the assignment. Submitted homework should include the names and netIds of both collaborators. Free deadline extensions apply to both partners.

Exams

There will be one in-class prelim and a final exam. The exam dates will appear on the schedule page as soon as they are known. Exams are open book and notes, closed Internet. Exams are cumulative.

There will also be occasional quizzes. The quizzes will be available on CMSX and can be done offline. Quizzes will not be counted in your grade (but you still have to do them).

Grading

Your course grade will be based on the homework, prelim, and final exam.

Regrades  If you believe your solution to a question was correct and it was marked incorrect, then you should write an explanation of the grading error and submit it as a regrade request in CMSX. You may also ask for a clarification. Regrade requests must be made within the deadline as posted on CMSX. Please note that partial credit is not negotiable.

Academic Integrity

The utmost level of academic integrity is expected of all students. Please read the following carefully.

On the homework, you may discuss general approaches and techniques with others, but the specifics of the solution must be developed between you and your partner. Under no circumstances may you submit work done with or by someone else under your own name or share solutions with anyone else except your partner.

You must acknowledge all sources apart from the course materials that you consulted, including Internet sources.

You may not use ChatGPT or any other generative AI.

You may not give nor receive assistance from anyone else during a quiz or an exam.

You may not give any hints or post any material that might be part of a solution publicly on Ed. If your question necessarily includes such material, post privately.

If you are unsure about what is permissible and what is not, please ask.

Special Needs

Students with Disabilities: Please register with Student Disability Services (SDS) to document your eligibility early in the semester, and let us know so that we have adequate time to arrange your approved accommodations.

Once SDS approves your accommodation, a letter will be emailed to you and the instructor. Please follow up with the instructor to discuss the necessary logistics of your accommodations. If you are approved for exam accommodations, please consult with the instructor at least two weeks before the scheduled exam date to confirm the testing arrangements.

If you experience any access barriers in this course, such as with printed content, graphics, online materials, or any communication barriers, please reach out to the instructor or your SDS counselor. If you need an immediate accommodation, please speak with the instructor after class or email the instructor and SDS at sds_cu@cornell.edu. If you have or think you may have a disability, please contact SDS for a confidential discussion: sds_cu@cornell.edu, 607-254-4545, sds.cornell.edu.