Course Details
Textbook
Overview
Two main questions arise with computational problem solving: can a problem be solved
at all, and if so, how efficiently? Topics include computability and complexity theory
as related to Turing machines, finite state automata, regular and contextfree grammars,
and the complexity classes of P and NP.
Prerequisites
CSC 207 or permission of instructor.
Quizzes and Participation
You are encouraged to attend class and participate in discussions.
Active participation in class discussions and short quizzes will
comprise 5% of your final grade.
Disabilities
Centenary assures students with disabilities equal opportunity to reach the same level of
achievement as other students. Strict confidentiality will be maintained on students with
disabilities. Services for students with disabilities are available through the Counseling
Center, located on the ground floor of Rotary Residence Hall, phone (318) 8695424.
Honor Code
All students are bound by the Honor System. The Honor System is applicable to all academic
work. See the
Centenary College Handbook
for the complete
Honor Code.
Extensions
Extensions for labs, projects, exams and quizzes 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.
 August 23: Chapter 1
 Sep 7: Chapter 2
Homework
You will have weekly Homeworks in this course, with problems assigned almost every day,
for a total of
50% of your final grade. You are required to present this work in class
through a writeup on the board and discussion with other students.
 HW1: Due Aug 26th
Pg 15, Section 1.1 Ex 25, 27, 28, 31, 35
Sample LaTeX File
 HW2: Due Sep 2th
Pg 28, Section 1.2 Ex 6, 7, 8, 9, 10
 HW3: Due Sep 13th
Pg 47, Section 2.1 Ex 6, 9, 10, 11, 15, 18, 20
 HW4: Due Sep 16th
Pg 55, Section 2.2 Ex 8, 11, 18
Pg 62, Section 2.3 Ex 3, 7, 8, 11, 12
 HW5: Due Sep 23rd
Pg 69 #2e, 4
Pg 76 #10, 14, 17, 20
 HW6: Due Sep 30th
Pg 28, Section 1.2 Ex 14, 15, 16, 21, 23
Pg 87, Section 3.2 Ex 5, 7, 8, 10
All homeworks must be written using LaTeX and
turned in as a PDF on the cs server.
There are many resources available for LaTeX on the web, including the LaTeX Math Symbols. Here are a few files that will
assist with creating your homework PDFs.
 hwsample.pdf
This PDF is an example of what your homework should look like when properly formatted
and compiled with LaTeX.
 hwsample.tex
This file includes the code for the LaTeX file.
 homework.sty, newalg.sty
Two style files with a few definitions for the homework layout.
 jflap.pdf
A figure to include in the homework pdf.
 jflap2dot.py
A utility file to convert the XML output of JFLAP into dot format, which
can be transformed into a pdf and then included in the LaTeX file.
Exams
There will be three exams, each worth 15% of your final grade. They will be takehome
oral exams and will cover material from the homeworks.
 Exam 1: Due October 11th
 Exam 2: Due November 10th
 Final: Exam Week Time
Grading
Your final grade for this course will be based on the Homework, Project, Exams and
Participation described above.
Grading Scale 
90100  A 
8089  B 
7079  C 
6069  D 
059  F 

Weights 
Homework  50% 
Participation  5% 
Exam 1  15% 
Exam 2  15% 
Final  15% 

© Mark Goadrich, Centenary College of Louisiana