Course Details
Textbook
Overview
Covers basic topics in automata, computability, and complexity theory, including:
models of computation (finite automata, Turing machines and RAMs); regular sets
and expressions; recursive, r.e., and nonr.e. sets and their basic closure
properties; complexity classes; determinism vs. nondeterminism, with and
without resource bounds; reductions and completeness; practice with NP and
Pcompleteness proofs; and the complexity of optimization and approximation problems.
By the end of this course, you should be able to:
 describe the relationship between formal languages and machines that can recognize them;
 describe the hierarchy of finite automaton, stack machines, and Turing machines;
 state the definitions of the primary concepts of the course, such as decidability, intractability,
determinism, computability, recursive enumerability, and the ChurchTuring thesis;
 understand the difference between decidable and undecidable problems;
 apply reducibility techniques to classify problems;
 classify a given decidable problem as belonging to P, NP, NPcomplete, or exponential time complexity classes;
 present a clear, concise solution to a problem in written form;
 present a clear, concise solution to a problem or summary of a topic orally.
Prerequisites
MATH 240.
Quizzes and Participation
You are encouraged to attend class and participate in discussions.
Active participation in class discussions and short quizzes will
comprise 15% of your final grade.
Disabilities
It is the policy of Hendrix College to accommodate students with disabilities, pursuant
to federal and state law. Students should contact Julie Brown in the Office of Academic
Success (505.2954; brownj@hendrix.edu) to begin the accommodation process. Any student
seeking accommodation in relation to a recognized disability should inform the instructor
at the beginning of the course.
Academic Honor
As stated in the
Hendrix Academic
Integrity Policy, all students have agreed to adhere to the following principles:
 All students have an equal right to their opinions and to receive constructive criticism.
 Students should positively engage the course material and encourage their classmates to do the same.
 No students should gain an unfair advantage or violate their peers' commitment to honest work and genuine effort. It follows that any work that a student submits for class will be that student's own work. The amount of cooperation undertaken with other students, the consistency and accuracy of work, and the testtaking procedure should adhere to those guidelines that the instructor provides.
 Members of the Hendrix community value and uphold academic integrity because we recognize that scholarly pursuits are aimed at increasing the shared body of knowledge and that the full disclosure of sources is the most effective way to ensure accountability to both ourselves and our colleagues.
I will provide guidelines for the amount of cooperation allowed on each assignment as
they are posted.
Extensions
Extensions are only given when
circumstances beyond your control (e.g. being sick, choir or sports travel)
prevent you from completing a project on time. You must notify me either by
email or phone of your circumstances well in advance of the due date.
Syllabus
We will be covering most of the textbook following the format in the table of contents.
We will also be using additional supplemental material such as relevant webpages
and background material.
Additional readings will be assigned before material will be covered in class. You are expected
to review the material and come to class prepared. As readings are assigned,
they will be posted
here.
 Chapter 1  Aug 31
 Chapter 2  Sep 4
 Chapter 5  Sep 11
 Chapter 6  Sep 11
Homework
You will have many many homework problems in this course, with problems assigned almost every day,
for a total of
55% of your final grade.
There will be individual as well as group portions to most homeworks. You are
required to complete all individual sections and your group section.
All homeworks must be written using LaTeX and
turned in as a PDF on Moodle.
There are many resources available for LaTeX on the web, including the
LaTeX Math Symbols,
Detexify,
and a WikiBook on LaTeX.
I recommend using ShareLaTeX to create your documents,
it is an online implementation of LaTeX that allows for collaboration.
Here is a great template
LaTeX file for homework assignments.
Groups
You will be rotating through assigned groups for your homeworks over the course
of the semester.
For each question, one member
of your group will be randomly chosen to present your group's work in class.
This presenter must also be prepared to answer
questions first from members of the other groups and then from the instructor.
The goal of these presentations is to work as a class and as a group to
teach each other the concepts in theory of computation and to improve
each other's presentation skills.
If the presenter is successful, all members of the group are awarded 3 points.
If there are minor errors in the written answer, the accuracy of the answer, or
the oral presentation skills, 0.5 points will be deducted from this team score.
If there are major errors in the written answer, the accuracy of the answer, or
the oral presentation skills, the question will be remanded to the team. In future
class sessions, this original presenter can ask to present their question again.
If successful after the second presentation, the group will earn 2 points. If there
are further concerns, the question will be once again remanded to the group, and can
be presented one more final time, where a successful presentation will earn the
group 1 point.
If any group member is absent from class
without a valid excuse when a group is awarded points, this member will receive 0 points.
1 point per individual per day will also be awarded for asking insightful questions
of presentations of other groups.
Your total points accumulated are divided by the total number of questions
your groups have been asked to answer, and then your final percentage for this
section is determined by the following formula (bounded below by 0 and above by 110).
Therefore, to earn the maximum number of points, you are responsible for ensuring
that all group members are prepared to accurately present
all questions assigned to your group, and that you engage other groups through
insightful questions and constructive feedback.
First Grouping
 Anderson, Jones, Nickle, Sarringar, Shaddox
 Bell, McAvey, Niyongabo, Sorey, Stransky
 Dye, Hoglan, Kou, Ndemeye, Rose
Second Grouping
 Bell, Hoglan, Kou, Niyongabo, Sarringar
 Anderson, Jones, Ndemeye, Sorey, Stransky
 Dye, McAvey, Nickle, Rose, Shaddox
Third Grouping
 Jones, Kou, McAvey, Ndemeye, Niyongabo
 Dye, Hoglan, Nickle, Sarringar, Stransky
 Anderson, Bell, Rose, Shaddox, Sorey
Exams
There will be three exams, respectively worth 10%, 15%, and 20% of your final grade. They will be takehome
exams and will cover material from the homeworks.
 Exam 1: Due September 23
 Exam 2: Due November 2
 Final: Due Friday Dec 11 5pm
Grading
Your final grade for this course will be based on the Homework, Exams and
Presentations described above.
Grading Scale 
90100  A 
8089  B 
7079  C 
6069  D 
059  F 

Weights 
Individual Homework  15% 
Group Presentations  40% 
Exam 1  10% 
Exam 2  15% 
Final  20% 

© Mark Goadrich, Hendrix College