Introduction to Theory of Computing
Location: Gates Hall G01
Lecture: MWF 11:15am - 12:05pm
Instructor: John Hopcroft
Office Hours: By Appointment
- 8/24: Website Up
- There will be no class on Friday 9/28
- Example for a PDA and CFG for the complement of "xx" here
- There will be no class on Monday 11/19. Please come to the classroom at 11:15 to hand in your homework.
This course will cover finite automata, nondeterminism, context free grammars, Turing machines, computability, and NP-completeness. This course does not have official textbook. If you want to access to a book we recommend Formal Languages and their Relation to Automata or Introduction to Automata Theory, Languages, and Computation any edition. We plan to grade holistically. For example, if a student does poorly on the first midterm, but brings his/her later grades up, we will give the later test scores more weight as this shows hard work on the student's part.
Midterms will taken in-class
- Midterm 1: Friday, September 14th
- Midterm 2: Friday, November 9th
- Midterm 3: Monday, November 26th
Exam regrade requests will be considered if:
There will be NO final exam, but there will be a third midterm on a date to be decided.
|HW1||Due Date: 8/31|
|HW2||Due Date: 9/10|
|HW3||Due Date: 9/17|
|HW4||Due Date: 9/24|
|HW5||Due Date: 10/1|
|HW6||Due Date: 10/10|
|HW7||Due Date: 10/15|
|HW8||Due Date: 10/22|
|HW9||Due Date: 10/29|
|HW10||Due Date: 11/05|
|HW11||Due Date: 11/19 (in class at 11:15)|
|HW12||Due Date: 11/30|
We recommend typesetting solutions in LaTeX or writing them neatly in dark pen; HW will be graded on BOTH Correctness and Neatness. If we cannot understand your solutions, we cannot give you points! Late HWs are NOT accepted unless the student has reasonable cause e.g. a doctor's appointment during class. Please put your NETID on your homework.
Regrade requests will be considered if:
|Professor||John Hopcroft||Office hours by appointment only|
|TA||Shir Maimon (sm2723)||Office hours by appointement|
|TA||Yuanxi Shen (ys448)||Office hours Fridays 9am-11am in Rhodes 572|
|TA||Huan Qi (hq38)||Office hours Thursdays 5pm-7pm in Rhodes 402|
|TA||Jared Junyoung Lim (jl3248)||Office hours Thursdays 5pm-6pm in Rhodes 412|
|TA||Sourabh Chakraborty (sc2356)||Office hours Sundays 4pm-6pm in Rhodes 572 (4-5:30pm on November 11)|
|TA||Ashley Yang (ay322)||Office hours Sundays 11am-1pm in Rhodes 572|
|TA||Neil Sun (ns664)||Office hours Thursdays 10am-12pm in Rhodes 405|
**This course follows the Cornell University Code of Academic Integrity. Each student in this course is expected to abide by the Cornell University Code of Academic Integrity. Any work submitted by a student in this course for academic credit will be the student's own work. Violations of the rules (e.g. cheating, copying) will not be tolerated.