CSCI 4333 - Theory of Computation

(Fall 2019: CRN 80195)

Printable Course Syllabus

Byron Jeff

Phone: 678-466-4411
Office: TBA
Office hours:
    MW 3:30 - 4:45 PM, T 12:30 - 1:45 PM, or open door

Note: the syllabus and schedule are subject to change.

Course Description (3-0-3)

Theory of Computation: s course is a study of the main areas of theoretical computer science and their hierarchical interconnections. Basic results relating to formal models of computation are studied, with emphasis on grammars and languages, finite automata, Turning machines, and computational complexity.

Course Objectives:

Students are expected to obtain a developing level of mastery in computer science. Students will demonstrate an emerging level of knowledge of a broad range of fundamental computer science concepts and topics. Students should show potential to perform independently and should exhibit a high level of reasoning, critical thinking and problem solving skills. Course objectives are listed for each CS program outcome: At the end of the course the student should be able to:
  1. Understand the basic theoretical models of computability: deterministic and nondeterministic finite automata, pushdown automata, and variants of Turing machines
  2. Design finite automata corresponding to given regular sets, and describe the regular set associated to a given finite automaton. Do the same with pushdown automata and context-free languages, and with Turing machines and recursively enumerable sets
  3. Comprehend and apply a number of algorithms such as: the subset construction to transform a indeterministic finite automaton into a deterministic one; the DFA state minimization to minimize the number of states in a deterministic finite automaton; and the conversion algorithms from regular expressions to finite automata and vice versa
  4. Understand limitations of finite automata (respectively, pushdown automata) and prove that some sets are not regular (respectively, context-free) by using the pumping lemma for regular languages (respectively, context-free languages)
  5. Simulate CFGs by NPDAs and vice versa, that is, convert a given context-free grammar to an equivalent nondeterministic pushdown automaton, and convert a nondeterministic pushdown automaton to an equivalent context-free grammar
  6. Apply algorithms to transform context-free grammars into normal forms such as the Chomsky and Greibach normal forms
  7. Prove that some problems are decidable or undecidable using techniques such as diagonalization and reduction

Program Outcomes:

The CS curriculum is built on six core program outcomes. Successful completion of this course will contribute to the following subset of these outcomes. Graduates will demonstrate a Mastery Level for the following outcomes:
  1. An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices;.
  2. An ability to apply design and development principles in the construction of software systems of varying complexity.
  3. An ability to design, implement, and evaluate a computer-based system, process, component, or program to meet desired needs.
  4. An ability to analyze a problem, and identify and define the computing requirements appropriate to its solution.


CSCI 2302: Data Structures

Meeting Times

Day of weekTimesCRNLocation
MW 2:10-3:25 PM 80195UC 322

Class Email: (80195 TR morning class)


Introduction to Languages and the Theory of Computation, 4/e (4th Edition) by Martin, McGraw Hill


You will have numerous opportunities to practice and demonstrate mastery of the materials covered in this course. It is up to you to keep current on all readings and assignments (including in-class announcements). *If you fall behind, you will most assuredly fail this course!*

Grading will be based upon the following scale:

A >= 90%
B 80% - 89%
C 70% - 79%
D 60% - 69%
F < 60%

Assignment weights are as follows:

AssignmentPortion of Grade
Final 30%
Three Monthly Tests 36% (12% for each of 3 tests given approximately once a month)
Review Quizzes12%
Project Portfolio (see details below) 12%
Practice Discussions (see details below) 10%

The final for this class is comprehensive. In addition the grade on the final can be used to redeem one *(and only one)* monthly test grade. So if your grade on the final is higher than your lowest monthly test grade, then that monthly test grade will be replaced with the grade from the final. This policy is designed to give a student the chance to improve one poor monthly test showing.

Partial credit may be given.

Course Topics

The list of course topics below will be presented in the order listed below. The listed exams are inserted following the likely coverage of the material that the exam will cover. Be aware that in class adjustments of both the material and the exam coverage may be made. Any in class adjustments superceeds the outline listed here. Exact test dates will be announced a minimum of one week before the actual exam.

Project Portfolio

Please read carefully!

A comprehensive student generated project portfolio must be submitted by each student on the specified date near the end of the semester. The portfolio consists of a number of required project elements coupled with additional project elements selected by the student. The portfolio will serve as the single grading instrument for the project portion of the course. The portfolio will be graded on the following elements:

Each element of the project portfolio will have a milestone/feedback deadline during the semester. Project elements that are substantively complete and correct (i.e. not perfect but mostly done) and turned in by the milestone/feedback deadline will receive feedback that the student may use to improve their project for the portfolio. However, any project element that is not submitted for feedback by the given deadline, or is not substantively complete/correct at that deadline will not receive credit for meeting the milestone/feedback deadline nor feedback incorporation element for that project element.

Practice Discussions

Practice is essential for learning success. When learning new skills that will be assessed on exams, be sure to practice examples in order to gain the confidence to perform that skill on the exam. Not all skills practice will be graded work. Nontheless, it is essential to practice skills for both understanding and mastery.

To facilitate this practice, each student is expected to participate in practice discussions. In practice discussions, each student must bring a problem for discussion, answer another student's problem, post the answer for their original problem, and discuss what was learned during the process. Practice problems cannot come from the book or examples of the course. Students are expected to use their internet search skills to find unique problems for the class to work on.

Practice discussions must be documented via the project portfolio. Each student must explain their problem they brought to the discussion and the problems they solved in the discussions. Grading will be based on both active participation in the practice discussions and quality of the problems brought to the disucssion and worked on in the discussion.

Active Feedback System

Soliciting and incorporating feedback is an essential element for success in the learning and development of technological systems. In order to encourage active student participation in the feedback process, this course implements an active feedback points system. The system is governed by the following rules:

Attendance Policy

Your active participation in class is expected. Class attendance is expected because it's much easier to learn if you're coming to class and asking questions in lecture about things that confuse you.

Late Work Policy

Late work delays both the learning process and the feedback process. Project elements needs to be turned in a timely fashion. D2L assignment submissions for project elements will be closed 24 hours after the feedback deadline.

The instructor may waive late penalties if techical problems to homework submission occurs. In the event of technical difficulties:


Academic Misconduct

Any student is found obtaining or granting inappropriate help in this course on any in-class graded assignment (test, quiz, exam) will subject to acadmic discipline. The offense will go on permanent record with the university. If this is not the student's first academic misconduct offense at CSU, he will be recommended for expulsion from the university. This is in full accord with CSU's policy, and we encourage you to read and review the university's policy in your student handbook.

So it is permissible to do group work or work with a tutor or other instructors on outside work in this course that is to be turned in for a grade. However, remember that the objective is to gain understanding of the problem solving process and apply that understanding. Note that the majority of the course grade is done via an in-class assessment, which each student must do on their own work without assistance.

Academic discipline can range from a zero for the in-class assessment in question to expulusion from the University depending on the circumstances.

All alleged instances of acadmic misconduct will be referred to the Office of Student Affairs.

CAS / Operation Study

Come to the CAS @ CSU

Throughout the fall, spring, and summer semesters, the Center for Academic Success (CAS) provides personalized one-on-one peer and professional staff tutoring in over 100 core subjects. We are located in Edgewater Hall Suite 276. The CAS also offers moderated study groups, informal study sessions, a comfortable study environment, a student study lounge, and it's all free! Come see us if you need help, come BE a tutor if you don't. Don't wait until it's too late. At the CAS, your academic success is right around the corner! For more information you can e-mail us at

Hardship Withdrawal

Students who experience an unexpected event or circumstance beyond their control that directly interferes with their ability to continue to make satisfactory progress in classes, such as serious illnesses or unexpected major life events, may petition the Dean of their major for a hardship withdrawal from all classes. In order to be considered for a hardship withdrawal, the student must have been passing all courses at the time that the emergency or other hardship arose and notify his or her instructors or other University officials about the hardship situation as soon as possible after it arose (per University and BOR policy, ―passing is defined as a grade of ―D or above). Hardship requests that are not filed in a timely manner are subject to denial even if the student was passing and the hardship was legitimate. Students who attend any classes through the end of a term and complete all course requirements (i.e. final project or exam) are not eligible for hardship withdrawal. If you have taken a final exam in any of your courses, you may not request a hardship withdrawal. For more information go to:

ITP Choice Information

Beginning Fall Semester 2001, all students at CCSU are required to state that they have on-demand access to a notebook computer that meets the recommended hardware/software specifications that have been established by Clayton State faculty. Academic penalties may be incurred for not meeting this requirement. See for more information.

Computer Skill Prerequisites

Students in this course must have the following prerequisite skills:

Disruption of the Learning Environment

Behavior which disrupts the teaching-learning process during class activities will not be tolerated. While a variety of behaviors can be disruptive in a classroom setting, more serious examples include belligerent, abusive, profane, and/or threatening behavior toward the instructor and/or other students in the class. A student who fails to respond to reasonable faculty direction regarding classroom behavior and/or behavior while participating in classroom activities may be dismissed from the class. A student who is dismissed from the class is entitled to due process and will be afforded such rights as soon as possible following dismissal, in collaboration with the Office of Community Standards. If found in violation, a student may be administratively withdrawn and may receive a grade of WF. More detailed examples of disruptive behavior are provided in the Code of Conduct and Disciplinary Procedures sections of the Clayton State University Academic Catalog and Student Handbook.

Weapons on Campus

Clayton State University is committed to providing a safe environment for our students, faculty, staff, and visitors. Information on laws and policies regulating weapons on campus are available at

Disability Services

Students with disabilities who require reasonable accommodations need to register with Disability Services (DS) in order to obtain their accommodations. You can contact them at 678-466-5445 or E-mail at .