CS 4810 - Introduction to Theory of Computing

General Information

You learn about models of computation and their relative power.


CS 2800 - Discrete Structures: Highly recommended to take first

Topics Covered

  • Regular Expressions 
  • Finite Automata 
  • Context-Free Languages 
  • Turing Machines 
  • Decidability 
  • P and NP


Weekly problem sets and three prelims. Very similar to CS 2800, maybe harder problem sets though.

General Advice

Pay attention and take notes in class. He often gives you slight variations of these topics in the homework, and they’re often not covered in the textbook.

The homework often has several trivial questions and one hard problem. Start thinking about the hard one ASAP.


If you liked CS 2800 this is a great course to take.

For the most part, this class was boring, since I already knew about most of the topics Hopcroft covered from other classes and random knowledge. I still managed to learn a lot, regardless of the class material.

Writing rigorous solutions for this class can be a pain in the ass. You can sometimes get away with a bit less rigor, but for your own purposes, you should at least know how to write a solution in full rigor.

Past Offerings

Semester Time Professor Median Grade Course Page
Fall 2017 - John Hopcroft ? http://www.cs.cornell.edu/courses/cs4810/2017fa/
Spring 2012 - John Hopcroft B+ http://www.cs.cornell.edu/courses/cs4810/2012sp/

Note: This will be offered in Fall 2013 on MWF at 9:05-9:55am.


Textbook: “Introduction to Automata Theory, Languages, and Computation” Hoprcoft, Motwani, and Ullman

Edit this page on Github: classes/CS4810.md

Edit me on GitHub