CSCI 4333 - Theory of Computation
(Fall 2021: CRN 82994/83075)
Phone: 678-466-4411 (Please leave a voicemail)
Office: UC 340
Office hours (In person, Teams or E-mail):
MW 2:30 - 3:30 PM, R 1:30 - 2:30 PM, or by appointment
Note: the syllabus and schedule are subject to change.
Course Description (3-0-3)
Theory of Computation:
This 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.
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:
- Understand the basic theoretical models of computability: deterministic
and nondeterministic finite
automata, pushdown automata, and variants of Turing machines
- 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
- 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
- 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,
- 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
- Apply algorithms to transform context-free grammars into normal forms
such as the Chomsky and Greibach
- Prove that some problems are decidable or undecidable using techniques
such as diagonalization and
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.Solve complex and significant problems with professional skill by
formulating efficient and effective algorithmic solutions to a wide variety
of sophisticated problems normally encountered in computing and in
3.Apply core concepts in computer science,
6.Demonstrate an ability
to acquire, interpret, and communicate results orally or in writing.
|Day of week||Times||CRN||Course Delivery Method|
|R|| 3:10-4:10 PM || 82994/83075||Asynchronous Online Content Delivery with In-Class Assessment/Project Activities|
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
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:
|Assignment||Portion of Grade
|Three Monthly Tests|| 36% (12% for each of 3 tests given approximately once a month)|
|Review Quizzes|| 16% |
|Project Portfolio (see details below)|| 12% |
|D2L online Discussions (see details below)|| 6% |
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.
Hybrid course delivery, assessment, and communication
The conversion of on campus classes to a hybrid online environment brings a
few challenges. These include course delivery, assessment, and
communications issues. This section addresses how these items will be
managed in this course.
The first issue is handling how to deliver instruction. My plan is to
generate a series of screencasts of course content and to make those
available via D2L. My expectation is that students would access these
videos asynchronously, at the time of their choosing within a certain
window. They will be posted into your D2L course. I plan to keep them
short, under 30
minutes each. As such you will be responsible for multiple content items
in a unit timeframe.
Assessment in an hybrid online environment is going to be a challenge. Normally
with an hybrid online class,
assessment would also be asynchronous, with wide time windows and time
limits. Something along the lines of having a week to take an assessment,
while having 90 minutes to do it after starting. Unfortunately, that setup
simply facilitates way too much information sharing among students which
makes it difficult to ascertain who actually knows what material. My plan
to combat this trend is to perform synchronous assessment at the
scheduled class times. This is the reason that the course is hybrid online but also
has an assigned class time. So everyone will get the test/quiz at
the same time at the beginning of the specified synchronous course time and have
limited time take it, and must turn it in at the
"end of class". Because of this, please plan to make available
the listed class time for such activities as review quizzes and tests.
These will be offered most weeks in the 2nd time slot (Wed or Thurs). There
may be an occasion assessment that will be slotted for the 1st time slot
(Mon or Tue).
Having done hybrid online classes before, I would like to point out the two
biggest challenges to operating in the hybrid online class environment. The first
is engagement. On campus classes facilitate a regular engagement of both
students and instructors because each have to be in a classroom at a
specific time. Just the action of being present facilitates engaging in the
material. Online decouples students (and the instructor), from that
sometimes passive engagement strategy. If you don't log in, review the
material, or do the work, then it's easy to become disconnected from the
course. I am asking that each of you plan to touch base with the course
every day, or at worst every other day in order to remain connected to the
activities going on in the class. In addition I will be rather insistent
about discussions in public forums as opposed to private discussions via
E-mail. The rationale is simply the fact that if the entire class can see a
productive discussion, then all class members can benefit from it. So
please expect that questions asked via E-mail will either be requsted, or
transferred by me, into the public discussion forums for the course.
The second challenge is communication. Again it is easier to communicate a
lot of information when gathered in a single spot for an extended period of
time. In the hybrid online environment, communication is a critical component. But
I admit that it can be a challenge for folks like me who are talkers, and
not writers. I plan to push communications via class E-mail and
answering questions in the Q/A discussion boards of each course. The Q/A
discussion boards are set up to deliver me an immediate notification to
shorten the turnaround time for answers. If you need
to communicate with me, use the Q/A discussion boards for each UNIT for items that are
relevant to the entire class, and CSU E-mail (not D2L e-mail please!) to
communicate personal or urgent issues. Like I expect from you, I'll be
checking into each class every day so you can expect 24 hour or less
turnaround to Q/A posted items. Be aware that the more you ask, or the more
complicated the issue, the longer it may take to get back to you.
For example 5 individual short posts/E-mails will likely get faster answers
than one single post/E-mail with all 5 items in it because I generally try
to solve all of the problems before answering.
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.
- Chapter 1: Basic Mathematical Objects
- Chapter 2: Finite Automata
- Test #1: Mid September
- Chapter 3: Regular Expressions, Nondeterminism and Kleene's Theorem
- Chapter 4: Context Free Languages
- Test #2: Mid October
- Chapter 5: Pushdown Automata
- Chapter 6: Context and Non-Context-Free Langauges
- Test #3: November 18th, 2021
- Chapter 7: Turing Machines
- Final Exam: December 2nd, 2021 Time: TBA
COVID-19 Health and Safety Syllabus Addendum
Clayton State University is committed to providing and promoting a healthy
and safe learning environment. All
students, faculty, and staff are expected to comply with all social
distancing mitigation measures, practices,
guidelines and policies. Please note the following rules and regulations
that are in place during the Fall 2021
semester due to the COVID-19 pandemic:
- Anyone who is feeling ill should refrain from coming to campus and should
consult the symptoms related
to COVID-19 to determine if a visit to a physician or clinic is necessary.
Any faculty, staff or student who is
exhibiting COVID-19 symptoms, has been sick with COVID-19 symptoms, tested
positive for COVID-19, or
has been potentially exposed to someone with COVID-19 (either through
community-related exposure or
international travel) should self-isolate or stay home and report their
case using the COVID-19 Reporting
Form. Faculty and staff should also notify their supervisor. Students
should consult with University Health
- For the health and safety of your fellow classmates and the campus
community, we strongly encourage you
to wear a face covering during class, during in-person office hours and
while inside campus facilities.
- Assigned seating will be used in all classes on campus, and attendance
will be taken on a daily basis.
Seating charts will be accessible through the D2L course space and should
be reviewed prior to the first day
of class. Students are to refrain from entering the instructor designated
space unless the instructor allows.
- Disinfecting wipes or other approved cleaning solutions will be available
to all students and faculty who
have an on-campus class.
- All persons are to adhere to the posted signs and directions in hallways
and buildings, except in the case of
fire or other emergency requiring evacuation.
- Students are not to enter rooms until 10 minutes before class and must
vacate the space at the end of
class. Any classrooms that are not in use for classes should be left vacant
unless prior scheduling approval
has been granted.
- To aid in ventilation of classrooms and to maximize air exchange rates,
classroom doors should be closed
during each class meeting and make sure they are closed after their class
concludes. Air purifiers should be
left on and will operate based on a sensor.
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.
- Project Completeness
- Project Correctness
- Meeting milestone/feedback deadlines (feedback information below)
- Incorporating project element feedback
- Documentation of project design and development
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
- Each student begins the semester with a one feedback points balance.
- For each course element that requires feedback, the student is
responsible for actively soliciting feedback for that element.
- Students may only solicit feedback for course elements that are turned
in a timely fashion before the given due date.
- Students who solicit feedback before the deadline gain one point on
their feedback balance. Students who do not solicit feedback, or turn in
their assignment late, lose one point from their feedback balance.
- Students who have a positive feedback balance gain two
rewards. The first is that students with a positive feedback balance may
request and receive feedback via E-mail. The second is that students with a
positive reward balance at exam time earn two extra credit points on their
- Students who do not have a positive feedback balance must solicit
feedback in person during office hours. In addition students who do not
have a positive feedback balance at exam time are not eligible for extra credit points
on their exam.
Your active participation in class is expected. Class attendance is
expected because it's much easier to learn if you're participating in
class and asking questions about things that confuse you.
- All excused absences must be accompanied by documentation such as a
- Any excused absence for a monthly test or final must be discussed with
the instructor at least 24 hours in advance. Test absences must be
documented beforehand. Test absences that do not follow the above procedure
will result in a grade of zero that that test or final.
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
The instructor may waive late penalties if techical problems to homework
submission occurs. In the event of technical difficulties:
- Please inform the instructor via E-mail of the problem.
- Please DO NOT SUBMIT any assignments VIA E-MAIL UNDER ANY
CIRCUMSTANCES! Assignments submitted via e-mail will not be accepted. All
assignments must be submitted via Desire2Learn.
Words of Wisdom (TAKE THIS PART SERIOUSLY!)
- In an online class reading for comprehension is critical. When working
through a new task with written instructions, please take the time to read
through all the instructions before beginning. You may even want to take
notes on what you are reading. Don't be the student who after reading the
instructions of "click this link, then click the blue button on the
resulting page" sends an e-mail asking "I clicked the link, what do I do
- Skills 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. It is essentially that
skills practice items be worked on before the assessments even though the
final assessment on those items occur at the end of the semester with the
- Start assignments early. This way, you can ask questions and clarify
things that are confusing. Be sure to take a look at the homework when you receive it and not an hour before it is to be turned in!
- If you cannot keep up with the pace of this class,
please talk with your professor as soon as possible. Please do not simply
drop the class without first discussing your situation.
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
So it is
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
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.
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:
- Able to use Windows operating system
- Able to use Microsoft Word word processing system
- Able to send and receive email using Outlook. Your instructor will
respond only to emails that originate from your Clayton State student
email. Use only your Clayton State to communicate information to your
instructor. D2L E-mail may have a slower response time than CSU E-mail
- Able to attach and receive attached files via email
- Able to use a Web browser
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
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