Introduction to the Theory of Computation (CS3240)

Course Information

Title: Introduction to the Theory of Computation
Institution: Metropolitan State University of Denver
Course ID: CS 3240, §1 & §2     (HON 3240)
Semester: Spring 2015

Tuesdays & Thursdays 2:00PM - 3:50PM
§1 Jan 20, 2015 - Mar 14, 2015
§2 Mar 16, 2015 - May 16, 2015

Location: Central 101
Credit Hours: 2
Prerequisites: CS 2050 and MTH 3170 with grades of "C" or better
Moodle Site: http://
Instructor: Dr. Jody Paul (schedule & office hours)
E-mail: jody @
Office: Science 1038 (x68435)
Campus Mail: Campus Box 38

Course Description

This course provides an introduction to the theory of computation through exploration of language theory and computability. It is concerned with the following:

  • What are the fundamental capabilities and limitations of computers?
  • What makes some problems computationally hard and others easy?

Language theory explorations will include expressions and formal representations of multiple categories of languages: regular, context-free, and recursively enumerable. Basic concepts in computability include: Universal Turing Machines, unsolvable problems, and intractable problems (NP-Completeness).

Participants are expected to have good working facility with the mathematical concepts and tools addressed in the prerequisite course MTH 3170 and its cascaded prerequisites. This course makes heavy use of formal logic, set theory, and formal proofs in working with functions, relations, graphs, induction, and recursion. Knowledge and skill in computer programming are likewise presumed, commensurate with the application of concepts from the prerequisite course CS 2050 and its cascaded prerequisites.

Note that this 2 credit-hour course is taught as a 4-hour course over half of a semester. The demands are thus equivalent to a 4 credit-hour course for the duration of that half-semester. A nominal expectation for students with strong prerequisite knowledge is a minimum of 8 hours per week outside of class (approximately 64 hours) in addition to the scheduled class time. Students with weaker prerequisite knowledge may find they need to invest substantially more time. N.B. Attendance during the first week of class is required (as specified in the MSU Denver Student Handbook Academic Policies for Students.


The final course grade is determined by combining the scores of assignments, the midterm exam, and the final exam using the following weighted distribution and conversion to letter grade. You are guaranteed a grade no lower than that computed by this weighted score and conversion of that score (percentage of total possible) to letter grade as shown.

Distribution (weights):
30% = Assignments
26% = Midterm
44% = Final Exam

The lowest assignment score will be dropped in computing the total for the Assignments category.

          A  : 93% ≤ score
          A- : 90% ≤ score < 93%
          B+ : 87% ≤ score < 90%
          B  : 83% ≤ score < 87%
          B- : 80% ≤ score < 83%
          C+ : 77% ≤ score < 80%
          C  : 73% ≤ score < 77%
          C- : 70% ≤ score < 73%
          D+ : 67% ≤ score < 70%
          D  : 63% ≤ score < 67%
          D- : 60% ≤ score < 63%
          F  : score < 60%

Textbooks & Software

Cover of Sipser book Introduction to the Theory of Computation (Third Edition)
by Michael Sipser
Cengage Learning (2012); ISBN 113318779X


Cover of JFLAP book JFLAP: An Interactive Formal Languages and Automata Package
by Susan H. Rodger and Thomas W. Finley
Jones & Bartlett Learning (2006); ISBN 0763738344

Pushdown Automaton JFLAP
A package of interactive graphical tools that aid in learning the basic concepts of formal languages and automata theory

Additional Course Policies


Extensive hands-on practice is necessary to achieve the required understanding of and ability to utilize the concepts in computer science theory. Such practice is correlated with successful performance on exams.

Assignments represent your opportunity to practice applying the concepts, thereby enhancing your understanding and helping you to identify questions regarding the concepts and their application.

The assigned exercises target these objectives. You are expected to work through all assigned exercises and are strongly advised to attempt as many additional exercises as you need to develop facility with the concepts and techniques.

JFLAP provides you with the direct means to objectively determine the correctenss of your work. Even where JFLAP files are not required to be submitted, you are expected to use JFLAP to verify your solutions. JFLAP is a valuable tool that supports your experimentation with and exploration of the course material.

Details regarding assignments and projects will be provided in class and on the course websites.

Online Submission

Assignments must be turned in using the course "moodle" website unless explicitly specified otherwise. In particular, e-mail and hard-copy will not be accepted in lieu of online submission. The Moodle assignment activity allows you to enter and upload working-drafts (such as work in progress that you do not intend to be assessed as the assignment submission). Therefore, to indicate that you wish your assignment entry to be accepted for assessment, you must click the Submit button for that assignment. Note that failure to click the Submit button will result in no earned score for the assignment. Note further that use of the Submit button indicates that the assignment is ready to be scored.

Due Dates/Times

Deliverables associated with assignments may be aubmitted for scoring at any time prior to the published due date/time.

No assignment deliverables will be accepted more than 24 hours after the published due date/time.

N.B. All risks associated with late submissions are assumed by the student. Note in particular that system and network failures occuring after the published due date/time will not result in an extension of the late submission acceptance period.

Illness, crises, and emergency situations will be dealt with on a case-by-case basis in accordance with University, School, and Departmental policies.

Deliverable Formats

Text-only documentation should be plain (unformatted) text in ASCII or UTF-8. If a diagram is part of the documentation then the file must be one of PDF, GIF, JPEG, PNG or ASCII text using fixed-width style character diagramming. (Specifically unacceptable formats include: Microsoft Word, Apple Pages, Microsoft Powerpoint) If an archive of multiple files is required, the format will be specified. JFLAP files must use the associated extension .jff

Note that a deliverable submitted in an unacceptable format is equivalent to no submission at all. Similarly, a submission with an incorrect name is likewise equivalent to no submission. If you are unsure about the acceptability of a file format or the specification of file name, please check with your instructor well before submission.

Class Sessions & Websites

You are expected to prepare in advance for class sessions (reading, exercises, etc.).

Substantial information is disseminated during class sessions and via the course websites. You are responsible for knowing this information whether or not you attended the sessions or accessed the websites.

In addition to important course and domain information, the course support website also provides the vehicle for managing assignments and assessment.

Collaboration & Citation of Sources

Collaboration is encouraged and regarded as an essential aspect of learning Computer Science and programming. Collaboration and discussion with fellow students and instructors concerning course information, materials, assignments, projects, proofreading, and concept exploration is strongly encouraged. You are not expected to learn the course content or work on assignments and projects in isolation on your own.

That said, you must generate your own submissions, reflecting your individual effort, for every assignment you turn in to be assessed, even if the outcome results from collaborative effort. You must also credit the people with whom you worked.

If you consult any sources, you must explicitly reference the sources and indicate where and how they apply.

Turning in work that does not credit collaborators, includes quotations without corresponding citations, or does not properly cite sources, must be treated as academic dishonesty and an attempt at fraud. All incidents of suspected dishonesty will be reported to the department and the Dean of the college. Consequences may include a score of 0 on the assignment, a grade of "F" for the course, academic probation, or dismissal from the institution. This is a very serious matter and should not be taken lightly. If you have any uncertainty or concerns, please discuss them with me or your advisor.

Note that collaboration is not acceptable during any exam.

Official Information

Official policies applicable to all courses:

MSU Denver College Catalog:
Official announcements, including Academic Policies and Procedures and Student Rights and Responsibilities

MSU Denver Academic Calendar:
Additional official dates and deadlines, including the last dates to withdraw and receive NC and holidays

MSU Denver Student Handbook:
Important Metro State and Auraria campus policies and procedures for students