Instructor: Prof. Katherine St. John
E-mail: stjohn at
Office: G 137D
Office Hours: Tuesdays, Thursdays 9:30-11am
Lecture: Tuesdays, Thursdays 11am-12:40pm

General Information


Undergraduate vs. Graduate Sections: The lectures for the undergraduate and graduate courses will be the same, but the class work, assignments, and exams of the two courses are different. While both the undergraduate and graduate courses assume fluency in a procedural programming language and discrete mathematics, the graduate course requires graduate-level programming skills and mathematical proofs.

Grading Policy

Grading: The grading for the course will be based on:

Problem Sets: Homework assignments are posted on the class website. Instead of turning in the whole problem set, each student will be responsible for presenting and writing up some of the problems (the top three grades will make up the assignment grade for the course). The written solutions will be posted on the Blackboard website for the class, so, they can used by everyone to study for the exams. Since it's hard to write down answers that are concise and are easily readable by all, if you wish to improve a grade on any problem, you may resubmit it for grading. Full credit will only be given for those solutions that are correct, clear, and concise. For programs, full credit will only be given for those that run correctly and have good documentation and programming style.

Class Work and Quizzes: Every class meeting there will be graded work or quizzes. There are 26 class meetings and 2 midterm exams over the course of the semester. The top 20 grades earned will make up the class work grade. The Blackboard honesty pledge quiz can also count for this grade if submitted by Friday of the first week.

Exams: The exams will be

Since the final is comprehensive, if you do better on it than on one of the midterm exams, the score on the final may replace one of the midterm scores. Note that the final will be long and difficult, so, it is an exceptionally bad idea to plan on taking advantage of this. There will be no makeup exams, and you must pass the final to pass the class.

Honor Code:

Materials, Resources and Accommodating Disabilities

Textbook: Introduction to the Theory of Computation, by Michael Sipser, Cengage Publishing, any edition (about $40 for second edition).

Use of Technology & Blackboard: All coursework is submitted via the Blackboard system, provided by CUNY to all enrolled students. If you have not accessed Blackboard or are having difficulties, contact Blackboard Support in the Information Technology Division. You can also visit the Help Desk in the Computer Center (first floor, Carman Hall) in person. They can reset passwords and help with simple Blackboard issues.

Accommodating Disabilities: Lehman College is committed to providing access to all programs and curricula to all students. Students with disabilities who may need classroom accommodations are encouraged to register with the Office of Student Disability Services. For more information, please contact the Office of Student Disability Services, Shuster Hall, Room 238, phone number, 718-960-8441.

Learning Objectives

At the end of the course, students should be able to:
  1. Describe finite state automatas and regular languages, and show their equivalence.
  2. Explain and use regular expressions ("regex") both theoretically and in parsing strings.
  3. Use the pumping lemma for both regular and context-free languages.
  4. Define decidability and solvability.
  5. Describe a Turing Machine and the Halting Problem.
  6. Use Big-oh notation to analyze algorithms.
Further, those enrolled in the graduate section, should be able to:
  1. Explain the Church-Turing Thesis.
  2. Prove the Halting Problem is undecidable.
  3. Demonstrate the difference between Big-oh and Small-oh notation in the analysis of algorithms.
This website for this class is located at: