CS 4810: Introduction to Theory of Computing

Instructor:
Dexter Kozen
kozen@cs.cornell.edu
436 Gates
255-9209 office
257-4579 home
592-2437 cell

Teaching Assistants:
Fran Mota
fa273@cornell.edu

Xiang Long
xl483@cornell.edu

Hon Wei Khor
hk634@cornell.edu

Rowan Meara
rrm89@cornell.edu

Shan Jiang
sj438@cornell.edu

Course Administrator:
Jessica Depew
401 Gates
jd648@cornell.edu

For office hours, please see Staff tab.

MWF 11:15am-12:05pm, 203 Phillips

We will be using Piazza as an online discussion forum. You are encouraged to post any questions you might have about the course material. The course staff monitor Piazza closely and you will usually get a quick response. If you know the answer to a question, you are encouraged to post it (but please avoid giving away any hints on the homework or posting any part of a solution--this is considered a violation of academic integrity).

By default, your posts are visible to the course staff and other students, and you should prefer this mode so that others can benefit from your question and the answer. However, you can post privately so that only the course staff can see your question, and you should do so if your post might reveal information about a solution to a homework problem. You can also post anonymously if you wish. If you post privately, we reserve the right to make your question public if we think the class will benefit.

Piazza is the most effective way to communicate with the staff and is the preferred mode of interaction. Please reserve email for urgent or confidential matters. Free-ranging technical discussions are especially encouraged. Broadcast messages from the course staff to students will be sent using Piazza and all course announcements will be posted there, so check in often.

We are using the course management system CMS for managing assignments, exams, and grades. Everyone who preregistered for the course should be entered, but if you did not preregister, you are probably missing. Please login [http://cms.csuglab.cornell.edu/] 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 the Course Administrator so that you can be registered.

You can check your grades, submit homework, and request regrades in CMS. Please check your grades regularly to make sure we are recording things properly. The system also provides some grading statistics. There is a help page with instructions.

Please do not repost course materials released on CMS publicly. These materials are intellectual property and meant for participants in the course. They are not free to the public.

Announcements and supplementary course material will be posted to the Resources page in Piazza. Homework and exam solutions will be available in CMS. Check frequently for new postings.

Required:
--D. C. Kozen. Automata and Computability. Springer, 1997.

We will follow the text fairly closely; check the table of contents for the syllabus. Supplementary topics will be covered as time permits.

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 in the Engineering library.

There will be 11 homework assignments consisting of 4-6 problems. Assignments and solutions will be posted in CMS.

Homework assignments may be done individually or in groups of two or three. Collaboration is encouraged. If you collaborate, submit one copy of your solutions with the names and netIds of all collaborators. You must register your group in CMS for each assignment. One of the group members must invite the others, and the others must accept the invitation. See the CMS online help for details. Please note that the preferred interpretation of working in groups is not, "Dick does problem 1 and Jane does problem 2," but rather, "Dick and Jane do problem 1 and Dick and Jane do problem 2."

You must submit your written solutions online via CMS in .pdf format. Only one group member need submit the file. We strongly prefer that you typeset your solutions using LaTeX, but scanned handwritten solutions are permitted as long as they are legible. In the latter case, please downsample before submitting. Follow the online instructions for submitting files. You may upload as many times as you wish. Only the latest version will be graded. After submitting your homework, please download it again or check the MD hash to be sure that the file you submitted was the one you intended to submit.

Acknowledge all sources, including others in the class from whom you obtained ideas and any Internet sources.

Homework due dates (subject to change):
HW1 Wed 2/3
HW2 Wed 2/10
HW3 Fri 2/19
HW4 Mon 2/29
HW5 Fri 3/11
HW6 Fri 3/18
HW7 Fri 3/25
HW8 Mon 4/18
HW9 Mon 4/25
HW10 Mon 5/2
HW11 Mon 5/9

Homework is due at 11:59pm on the due date. You will have a short unspecified grace period during which you will still be able to submit without penalty, but we will post solutions within a day or two after the deadline, and no more submissions will be accepted after solutions are posted. Please note that the late homework deadline as indicated in CMS is irrelevant.

There will be two in-class prelim exams and a final. Exams are open book and notes, closed Internet. All exams are cumulative.

Prelims:
P1 Fri 3/4
P2 Mon 4/11
Final exam: Mon 5/16, 9am, Hollister B14

Homework 40%, prelims 15% each, final 30%.

Homework regrade requests can be submitted electronically in CMS. Exam regrades should be handwritten and submitted to the course staff. Regrades should be submitted within one week of the date the scores are released. Please include a description of the grading error with your regrade request. Partial credit is not negotiable.

The utmost level of academic integrity is expected of all students. Academic integrity is rarely an issue in upper level courses, but unfortunately it does arise from time to time, so we want to be clear.

Under no circumstances may you submit work done with or by someone else under your own name or share detailed proofs with anyone else except your partner(s). However, general questions regarding proof techniques or the requirements of the assignment are permissible.

You must cite all sources, including Internet sources. You must acknowledge by name anyone whom you consulted.
You may not give nor receive assistance from anyone else during an exam.
You may not give any hints or post any material that might be part of a solution publicly on Piazza. If your question necessarily includes such material, post privately.

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

Academic Integrity Resources:
--Cornell University Code of Academic Integrity [http://cuinfo.cornell.edu/aic.cfm]
--Computer Science Department Code of Academic Integrity [http://www.cs.cornell.edu/undergrad/CSMajor#ai]
--Explanation of AI Proceedings [http://www.theuniversityfaculty.cornell.edu/AcadInteg/]

We provide appropriate academic accommodations for students with special needs and/or disabilities. Requests for academic accommodations are to be made during the first three weeks of the semester and must be accompanied by official documentation. Please register with Student Disability Services [http://sds.cornell.edu] in 420 CCC to document your eligibility.