CS 4810

Introduction to Theory of Computing

Location: Gates Hall G01
Lecture: MWF 11:15am - 12:05pm

Instructor: John Hopcroft
Office Hours: By Appointment

Announcements

  • 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.

Concepts

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.

Exams

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:

  • They are handed to Prof. Hopcroft or TAs within one week of the time that the given exam is returned to the class.
  • The answer was falsely graded as incorrect. In particular, we will not accept requests for higher partial credit.
  • They come with a written explanation, stapled onto the exam, of why the given answer was right.

    • There will be NO final exam, but there will be a third midterm on a date to be decided.

    Homework

    HW1 Due Date: 8/31 PDF
    HW2 Due Date: 9/10 PDF
    HW3 Due Date: 9/17 PDF
    HW4 Due Date: 9/24 PDF
    HW5 Due Date: 10/1 PDF
    HW6 Due Date: 10/10 PDF
    HW7 Due Date: 10/15 PDF
    HW8 Due Date: 10/22 PDF
    HW9 Due Date: 10/29 PDF
    HW10 Due Date: 11/05 PDF
    HW11 Due Date: 11/19 (in class at 11:15) PDF
    HW12 Due Date: 11/30 PDF

    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:

  • They are handed to Prof. Hopcroft or TAs within one week of the time that the given homework is returned to the class.
  • The answer was falsely graded as incorrect. In particular, we will not accept requests for higher partial credit.
  • They come with a written explanation, stapled onto the assignment, of why the given answer was right.

    • Course Staff

    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.