Cornell Computer Science Wikia

CS 4810 - Introduction to Theory of Computing

70pages on
this wiki
Add New Page
Comments0 Share

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

General Information Edit

You learn about models of computation and their relative power.

Prerequisites Edit

CS 2800: Highly recommended to take first

Topics Covered Edit

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

Workload Edit

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

General Advice Edit

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.

Testimonials Edit

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

Semester Time Professor Median Grade Course Page
Spring 2012 John Hopcroft B+
  • Note: This will be offered in Fall 2013 on MWF at 9:05-9:55am.

Resources Edit

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

Also on Fandom

Random Wiki