CS 4810

Introduction to Theory of Computing

Location: Phillips 203
Lecture: MWF 11:15am - 12:05pm

Instructor: John Hopcroft
Office Hours: By Appointment

Announcements

  • 12/04: The notes on oracles are available here.
  • 12/02: The topics that have been covered during the semester can be found here.
  • 10/16: The topics for the second midterm can be found here. A more detailed version can be found here
  • 9/12: The topics for the first midterm can be found here
  • 8/28: Website Up

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 27th
  • Midterm 2: Wednesday, October 23th
  • Midterm 3: Monday, December 9th

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: 9/9 PDF
    HW2 Due Date: 9/13 PDF
    HW3 Due Date: 9/20 PDF
    HW4 Due Date: 9/27 PDF
    HW5 Due Date: 10/04 PDF
    HW6 Due Date: 10/11 PDF
    HW7 Due Date: 10/18 PDF
    HW8 Due Date: 11/04 PDF
    HW9 Due Date: 11/08 PDF
    HW10 Due Date: 11/15 PDF
    HW11 Due Date: 11/22 PDF
    HW12 Due Date: 12/06 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 Pedro Amorim (pa395) Office hours by appointement
    TA Caleb Koch (cak247) Office hours Fridays 2:30 - 4:30pm (Kimball B11)
    TA Nathaniel Kinzly (nrk42) Office hours Thursdays 6 - 7pm (Rhodes 412)
    TA Chaska Yamane (cky24) Office hours Thurdays 10:30 - 11:30 am (Rhodes 597) or by appointment
    TA Christopher Watson (cw723) Office hours Tuesdays 12 - 1pm (Rhodes 712)


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