CS 4810 - Introduction to Theory of Computing

General Information

You learn about models of computation and their relative power.

Prerequisites

CS 2800 - Discrete Structures: Highly recommended to take first

Topics Covered

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

Workload

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.

Testimonials

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

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

Resources

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