Special COVID-19-related information for S22
Due to ongoing health concerns, Cornell has mandated that all classes be virtual for the first two weeks of the semester. Our first four lectures will be online via Zoom. The current plan is to resume in-person instruction on Feb 7, which means if all goes well, our first in-person lecture will be Tuesday, Feb 8 in Olin 255.
Office hours for course staff will be by Zoom as well until Monday, Feb 7.
Everyone is expected to abide by the university public health requirements at all times. See this page for the latest information. Please notify the course staff if you become ill and/or are placed in isolation or quarantine. Do not attend class if you are ill.
Enrollment information for S22
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 9:40–10:55am, Olin 255 (in-person starting Tue Feb 8, online via Zoom until then).
Permanent Zoom link: https://cornell.zoom.us/j/93585746762?pwd=TTJTNUY0b21IbUM0bVJDUnBMcC9BQT09
Instructions for phone access here.
Lectures will be given live during this time and you are expected to attend if you are able. Lectures will also be broadcast via Zoom for those who cannot attend in person. Lectures will not be recorded.
[mouse over for email]
or by appt
|Zoom (before 2/8)
436 Gates (from 2/8)
[mouse over for email]
[mouse over for email]
||Zoom (before 2/8)
408 Rhodes (from 2/8)
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.
- D. C. Kozen. Automata and Computability. Springer, 1997.
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.
- J. E. Hopcroft, R. Motwani, J. D. Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd ed. Addison-Wesley, 2007.
- M. Sipser. Introduction to the Theory of Computation, 3rd ed. Cengage Learning, 2012.
- H. Lewis, C. Papadimitriou. Elements of the Theory of Computation. Prentice-Hall, 1997.
- M. A. Harrison. Introduction to Formal Language Theory. Addison-Wesley, 1978.
- N. J. Cutland. Computability. Cambridge University Press, 1980.
These titles are on reserve at the Engineering library.
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.
Supplementary course material will be posted on the handouts page. Check often for new postings.
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.
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 should be one of them. If not, please send your full name and Cornell netId to Corey (mouse over for email) so that she can register you.
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.
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.
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 (including Covid-19) 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 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. It should include the names and netIds of both collaborators.
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. All 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).
Your course grade will be based on the homework, prelim, and final exam.
- 50% homework
- 20% prelim
- 30% 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.
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 outside sources (apart from the course materials) that you consulted, including Internet sources.
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.
- Cornell University Code of Academic Integrity
- Computer Science Department Code of Academic Integrity
- The Essential Guide to Academic Integrity at Cornell
Students with Disabilities: Your access in this course is important to us. 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 academic 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.
Efforts have been made to comply with all accessibility requirements. 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 right away. If you need an immediate accommodation, please speak with the instructor after class or email the instructor and SDS at email@example.com. If you have or think you may have a disability, please contact SDS for a confidential discussion: firstname.lastname@example.org, 607-254-4545, sds.cornell.edu.