CSC 240

Theory of Computation

Course Syllabus

At the conclusion of this course, the diligent student will be conversant in major topics related to computational theory, including: formal models of computation, the Church-Turing thesis, Time and Space complexities, as well as Reducibility and Intractability.

The two most vitally important tips I can give you for success are:

  1. Do not miss class. Missing a class in this course will make your life difficult. Missing two or three could be catastrophic.
  2. Start the homework early. The homework is hard. Waiting to start it until the night before it is due will almost certainly lead to failure.

Some of the assignments in the course will require writing code in C++. If your only programming experience up to this point is Java, you may find this Java to C++ reference page helpful.

Textbook

The textbook for this course is Introduction to the Theory of Computation, 3rd Edition by Sipser.

Though not required, you might also want to pick up a copy of How to Read and Do Proofs: An Introduction to Mathematical Thought Processes by Solow.

About the Instructor

Dr. Falin

Dr. Lee Falin worked as a software engineer in industry for several years before completing his Bachelor’s of Computer Science at the University of Illinois, then going on to complete a PhD in Genetics, Bioinformatics, and Computational Biology at Virginia Tech.

After completing his PhD, he worked as a Bioinformatician at the European Bioinformatics Institute, while continuing to work and teach in the private sector.

He has launched a couple of micro-ISV startups, and taught at Virginia Tech, BYU-Idaho, and Southern Virginia University.

Dr. Falin’s research interests include machine learning, bioinformatics, software entrepreneurship, and education. Dr. Falin and his wife have five awesome children whom they homeschool.

Prerequisites

Prior to taking this course, you should have completed CSC 220 - Data Structures and Algorithms (formally numbered as CSC 324), and Discrete Mathematics - CSC222 / MAT 332.

Grading

Assignments are weighted as follows:

For more information about late work, and other course policies, please see the Course Policies section.