Syllabus

	OTTERBEIN COLLEGE MATHEMATICAL SCIENCES DEPARTMENT C SC 381 Theory of Computation Spring 2008
	Class	MWF 2:00 - 2:50 p.m. in Towers 119
	Class Web Page	http://www.otterbein.edu/home/fac/dvdjstck/csc381/LinkFrames.htm
	Instructor	David J. Stucki
	Office	Towers 133
	Office Hours	M 3:00 - 4:00, W 1 - 2, R 12:30 - 1:30, or by appointment
	Email	DStucki@otterbein.edu
	Phone	823-1722
	Home Phone	878-8002 (After 9 a.m. and before midnight, please)

"Every mature scientific and engineering discipline recognizes the value of theory; it provides a stable intellectual foundation to the field. Theoretical computer science plays this role for computer science.

"Research in theoretical computer science has produced efficient data structures and algorithms that have been incorporated into many software tools and hardware products. Research in theory has also established conditions under which efficient algorithms do not or are unlikely to exist, and has set limits on the performance of algorithms and machines.

"Theoretical computer science provides the fundamental concepts, principles, and techniques needed to understand and cope with our rapidly changing field. Consequently, theory occupies a central place in computer science curricula. Theory courses on data structures, analysis of algorithms, and models of computation support and complement other computer science courses. Most theory courses strongly emphasize abstract reasoning and rigorous thinking, skills that are useful in a wide range of situations.

"The perspective on computers, programs and computation provided by theory is the best vantage point from which to uniformly understand all the developments in computer science."

—Statement on the Importance of Theoretical Computer Science,
SIGACT News, ACM, 1994.

Description	Models of computation based on machine models and formal grammars: finite automata; regular languages, pushdown automata, context free languages, Turing machines, recursive languages, and recursively enumerable languages; the Chomsky hierarchy of languages; the Church-Turing thesis; introduction to the halting problem and computability issues.
Prerequisites	Math 165, C SC 205
Text	Elements of the Theory of Computation , 2^nd ed. Harry R. Lewis & Christos H. Papadimitriou, Prentice-Hall, 1998. Amazon.com: $103.00 (new) $37.94 (used) BestBookBuys.com best price: $27.14 Otterbein Bookstore: $107.50 (new) $80.75 (used)
Work Load	"Students are expected to spend three hours per week (including class hours) in study for each quarter hour of credit attempted." (From p. 278 of the Course Catalog, Autumn, 2003 - Spring, 2005, Otterbein College Bulletin, Vol. LXXXV.) Since C SC 381 is 3 (Quarter) Credit Hours, 90 hours of study is expected: 30 hours in class (3 hours per week in lecture and lab), and 60 hours beyond class hours (6 hours per week).
Exams & Quizzes	There will be two midterm exams and a final. These will be closed-book exams. They will cover lecture material, readings, and questions regarding the homework. Make-ups will be scheduled only for documented emergencies. If you can document that you have three or more exams scheduled for the same day I will attempt to arrange for an alternate time only if given at least a week's notice. Quizzes will be given on an as needed basis (to be determined by me).
Homework	Regular homework assignments will be made. These assignments will include reading from the text, preparation of discussion questions, and problems to solve.
Participation	We pose and solve problems in a social context. Therefore, we need each other. This need is the reason we have classroom and lab sessions. *Attendance is required.* Each time you are absent without advance permission, you will lose 1% of your grade up to a maximum of 3% (taken from the participation category). Each student is expected to participate in the class discussions throughout the semester. To this end, all assigned readings for each day should be completed before the class period in which they are discussed.
Submissions	All submissions must be either word processed or neatly handwritten on single-sided lined paper. No spiral paper will be accepted. If you require more than a single sheet of paper, paper-clips are the preferred mechanism for securing all of the pages together.
Academic Misconduct Policy	All members of the Otterbein College community of learners are expected to follow the rules and customs of proper academic conduct. Proper conduct includes avoiding academic misconduct as defined in the Student Life Handbook. Students are encouraged to help each other learn the course material. Unless specifically prohibited, you may discuss homework problems and lab exercises with one another. Participants in these discussions usually enjoy the benefit of deeper and greater learning. However, all work submitted for evaluation that is based on discussions with others must be your own work; created with your own hands and fingers while thinking it through. Any work submitted for evaluation that includes work done by another, copying of another's work, or the result of following another's step-by-step keystrokes and mouse clicks, is a case of academic misconduct. When academic misconduct is found in any assignment or examination you submit, you will receive a zero grade for that assignment or exam. The misconduct will also be reported to the Office of the Academic Dean. If a previous academic misconduct offense is on your record, you will receive a grade of F for this course and a referral to the judicial system.

Grading	Assignment	Weight	Range	Grade	Range	Grade
	Homework	15%	93 - 100%	A	73 - 76.9%	C
	Quizzes	20%	90 - 92.9%	A-	70 - 72.9%	C-
	Midterm exams	30%	87 - 89.9%	B+	65 - 69.9%	D+
	Final exam	30%	83 - 86.9%	B	60 - 64.9%	D
	Participation	5%	80 - 82.9%	B-	0 - 59.9%	F
			77 - 79.9%	C+

Return to David J. Stucki's Home Page