CS483 - Theory of Computation

Spring-2024

Classes: TR 4:30pm - 5:45pm, Maria Sanford Hall 119
Instructor: Dr. Zdravko Markov, MS 30307, (860)-832-2711, http://www.cs.ccsu.edu/~markov/, e-mail: markovz at ccsu dot edu
Office hours: MW 4:30pm-6:00 pm, TR 10:45am-12:00pm, in person. Book an appointment here.

Catalog description: The concept of algorithm, correctness and efficiency of algorithm, decidable vs. undecidable problems, recursion, halting problem, formal languages, context free and context-sensitive grammars, and introduction to automata and parallel algorithms.

Course Prerequisites: CS253 and (MATH217 or MATH218)

Prerequisites by topic

Course description: The course covers the mathematical foundations of computing by discussing the following major topics:

Course Learning Outcomes (CLO)

  1. Gain proficiency with mathematical tools and formal methods
  2. Understand finite automata and formal languages
  3. Understand the equivalence of pushdown automata and context-free languages
  4. Understand Turing Machines and recognizable and decidable languages
  5. Describe unrecognizable languages and undecidable problems
  6. Analyze algorithm complexity and undestand the basics of complexity theory

Student Outcomes (SO) supported by the Course Learning Outcomes

Required textbook: Michael Sipser, Introduction to the Theory of Computation, 3rd edition, Cengage, 2013

Class Participation: Active participation in class is expected of all students. Regular attendance is also expected. If you must miss a class, try to inform the instructor of this in advance. In case of missed classes and work due to plausible reasons (such as illness or accidents) limitted assistance will be offered. Unexcused absences will result in the student being totally responsible for the make-up process.

Course Expectations for Out-of-Class Work: To succeed in this 3-credit class, it is expected that you commit a total of 12 hours per week to master the course material. This includes 2.5 hours of lecture time and an additional 9.5 hours dedicated to independent study and coursework. This time commitment aligns with the expectations set by the Computer Science department for major courses and adheres to university policies. Recognizing that dedicating this amount of time outside the classroom is a significant commitment, it is nevertheless necessary for success. Please plan your course load accordingly.

Grading: Grading will be based on six homework assignments (60%), a midterm test (20%), and a final exam (20%). The assignments and tests are listed in the tentative schedule of classes below and will be made available and submitted via Blackboard at https://ccsu.blackboard.com. The letter grades will be assigned according to the following table:

A
A-
B+
B
B-
C+
C
C-
D+
D
D-
F
95-100
90-94
87-89
84-86
80-83
77-79
74-76
70-73
67-69
64-66
60-63
0-59

Unexcused late submission policy: Submissions made more than two days after the due date will be graded one letter grade down. Submissions made more than a week late will receive two letter grades down. No submissions will be accepted more than two weeks after the due date.

Honesty policy: The CCSU honor code for Academic Integrity is in effect in this class. It is expected that all students will conduct themselves in an honest manner and NEVER claim work which is not their own. Violating this policy will result in a substantial grade penalty, and may lead to expulsion from the University. You may find it online at http://web.ccsu.edu/academicintegrity/. Please read it carefully.

Students with disabilities: Students who believe they need course accommodations based on the impact of a disability, medical condition, or emergency should contact me privately to discuss their specific needs. I will need a copy of the accommodation letter from Accessibility Services in order to arrange class accommodations. Contact Office of Accessibility Services, Willard-DiLoreto Hall, Suite W201 if you are not already registered with them. Office of Accessibility Services maintains the confidential documentation of your disability and assists you in coordinating reasonable accommodations with your faculty.


Schedule of classes and assignments

Note: Links to Lecture Notes and the dates for classes, assignments, and tests are available in Blackboard.
  1. Introduction: Automata, Computability, and Complexity. Reading: Section 0.1
  2. Mathematical Notions and Terminology. Reading: Section 0.2
  3. Definitions, Theorems, and Proofs. Reading: Sections 0.3 - 0.4
  4. Finite Automata. Reading: Section 1.1
  5. Assignment 1 due
  6. Nondeterminism. Reading: Section 1.2
  7. Regular Expressions. Reading: Section 1.3
  8. Nonregular Languages and the Pumping Lemma. Reading: Section 1.4
  9. Assignment 2 due
  10. Context-Free Grammars. Reading: Section 2.1
  11. Pushdown Automata. Reading: Section 2.2
  12. Introduction to Turing Machines. Reading: Section 3.1
  13. Examples of Turing machines, Recognizable and Decidable Languages. Reading: Section 3.1
  14. Assignment 3 due
  15. Variants of Turing Machines. Reading: Section 3.2
  16. Multi-Tape TM and Non-Deterministic TM Equivalence with TM. Reading: Section 3.2
  17. Definition of Algorithm. Reading: Section 3.3
  18. Examples of Decidable Languages. Reading: Section 4.1
  19. Assignment 4 due
  20. Midterm Test due
  21. The diagonalization method. Reading: Sections 4.2
  22. An undecidable language. Reading: Sections 4.2
  23. A Turing-unrecognizable language. Reading: Sections 4.2
  24. Reducibility. Reading: Sections 5.1
  25. Undecidable Problems from Language Theory. Reading: Sections 5.1
  26. Assignment 5 due
  27. Measuring Complexity. Reading: Section 7.1
  28. The Class P. Reading: Section 7.2
  29. The Class NP. Reading: Section 7.3
  30. NP-completeness. Reading: Section 7.4
  31. Assignment 6 due
  32. Final Exam due