CS 4810

Introduction to Theory of Computing

Location: Gates Hall G01
Lecture: MWF 11:15am - 12:05pm
Write the NetID in your HW

Instructor: John Hopcroft
Office Hours: By Appointment

Announcements

  • 21/8: HW 1 Posted
  • 27/8: HW 2 Posted
  • 30/8: Update: HW2 due date is Sept. 6
  • 1/9: Update: 5th question in HW2
  • 4/9: HW3 Posted
  • 8/9: HW4 Posted
  • 17/9: HW5 Posted
  • 22/9: HW6 Posted
  • 3/10: HW7 Posted
  • 12/10: Office hour of Joshua is changed to 4pm-5pm on Friday only in this week.
  • 13/10: HW8 Posted
  • 13/10: The Second Midterm Exam is on next Wednesday Oct. 18.
  • 14/10: Matt Habel will cancel his office hour on this Sunday.
  • 22/10: HW9 Posted
  • 28/10: HW10 Posted
  • 1/11: Yan and Joshua will cancel their office hour only in this week.
  • 2/11: HW11 Posted
  • 9/11: Yan and Matt Zhang will cancel their office hour only in this week.
  • 11/11: HW12 Posted
  • 16/11: Yan will cancel his office hour only in this week.

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

There are now three midterms. The midterms will be in class

  • Midterm 1: Sept. 29
  • Midterm 2: Oct. 18
  • Midterm 3: Nov. 20

Exam Regrade Policy:

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 normally do not accept requests for higher partial credit.
  • They come with a written explanation, stapled onto the exam, of why the given answer was right.

    • Homework

    HW1 Aug. 28 Download
    HW2 Sept. 6 Download
    HW3 Sept. 11 Download
    HW4 Sept. 18 Download
    HW5 Sept. 25 Download
    HW6 Oct. 2 Download
    HW7 Oct. 13 Download
    HW8 Oct. 23 Download
    HW9 Oct. 30 Download
    HW10 Nov. 6 Download
    HW11 Nov. 13 Download
    HW12 Nov. 20 Download

    HW Notes:

    Students should finish their work independently. Homeworks are due during class on the due date listed inside the chart above.

    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.

    HW Regrade Policy:

    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 Haobin Ni Wednesday 7:00pm-8:00pm, Gates Hall G13
    TA Daniel Sainati Thursday 5:00pm-7:00pm, Gates Hall G17
    TA Yan Wang Friday 9:00am-10:00am, Gates Hall G11
    TA Joshua Hull Friday 4:00pm-6:00pm, Gates Hall G19
    TA Matt Zhang Saturday 2:00pm-4:00pm, Gates Hall G15
    TA Matt Habel Sunday 8:00pm-10:00pm, Gates Hall G11

    Please email haobin.ni@gmail.* or yw763@cornell.* for any administrative questions/inquiries.
    For the homework questions, please email msz45@cornell.edu, dhs253@cornell.*, jth242@cornell.* or mah433@cornell.*.


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