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

## 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:

## 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 |

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

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