Instructor: Martha O'Kennon, Palenske 305.  
Office hours:  MWF 1:10 - 2:00, or by appointment (please make or verify appointments by e-mail)
E-mail:  mokennon@albion.edu

Text:  Introduction to Computer Theory (Second Edition) by Daniel I. A. Cohen, Wiley, 1997

Desirable Prerequisites:  Some mathematical maturity (what constitutes a correct proof, etc.) which would be evidenced by successful completion of Math 236 (linear algebra) and Math 239 (discrete math) or Math 335 (Abstract Algebra).  Familiarity with programming constructs such as recursion and looping and basic algorithm analysis, such as are learned in Math 173.

About this course.  It deals with the theoretical underpinnings of computer science, and has direct applications to such studies as programming languages, compiler design and algorithmic analysis.  It is probably more like linguistics than any of the other more computing-oriented computer courses you have seen at Albion. (I use many of its ideas in my studies in applied linguistics, and if you took CS 271 you will recognize some of them.) We will study several classes of computer languages, and the corresponding classes of theoretical machines that recognize the language (either accept an input string as grammatically correct or accept the string and produce some kind of appropriate output).  We will also study a type of machine that allows us to classify certain classical algorithms for time or space efficiency, and we will devote a brief time to these algorithms.

This text was chosen because of the large number of readable examples of each concept. Although some of the chapters are long, they are meant to be read each day before the lecture on the chapter, and then re-read after the lecture.  You should count on reading a couple of hours between classes.  I will be available by appointment for help on homework, or at the posted office hours.

Attendance is mandatory. You are responsible for all material covered in class, whether or not it is in the book.  

No make-up exams will be given. If you must miss an exam due to a death in the family or serious medical problem beyond your control, I will base your grade for the material on that exam on your final exam and other work in the class. You must pass the final exam to pass the course.

How your grade is computed.  Exercises will be assigned from each chapter, and will be collected weekly.  Exercises will contribute up to 25 points toward your final mark. There may be one or more (programming or other) projects assigned.   Projects will contribute up to 25 points, depending on how many there are.  There will be three tests (each worth 20 points) and a final exam (worth 30 points).  Some of these tests may be take-home and may or may not be group efforts.  At the end of the term, I will compute a weighted average, and final grades are assigned according to the following table.

4.0         See below
3.7         88-93%
3.3         84-87%
3.0         80-83%
2.7         78-79%
2.3         74-77%
2.0         70-73%
1.7         68-69%
1.3         64-67%
1.0         60-63%

Please note that the grade of 4.0 is reserved for students who have, in the words of the Academic Catalog, "independently sought out and used additional related materials, demonstrating the ability to discover new data, to develop new insights, and to bring them to bear on the work at hand."

Board Points. I will keep track of your trips to the board to present problems in a clear and understandable manner.  Each 5 board points will contribute 2 percentage points to be added to your final average, and will earn you a handsome certificate.  You may earn up to two certificates, but of course participate as much as you like!  

Tentative Syllabus:

Week 1  (begins Monday, January 13): Chapters 1 - 4
Week 2  (Tuesday, January 21): Ch. 5, 6 (Monday is MLK Holiday)
Week 3 (January 27):  Ch. 7 -8
Week 4 (Feb. 3):  Ch. 8. 9, Review for test #1
Week 5 (Feb. 10):  Test #1 (Monday, Feb. 10), Ch.10,11
Week 6 (Feb. 17):  Ch. 12,13
Week 7 (Feb. 24):  Ch. 13, 15
Week 8 (Mar. 3): Ch. 15, 16
(Spring Break: Monday, March 10- Friday, March 14)
Week 9 (Mar. 17):  Ch. 17.18, Review
Week 10 (Mar. 24):  Test #2 (Monday, March 24), Ch. 19, 20
Week 11 (Mar. 31):  Ch. 20, 21
Week 12 (Apr. 7):  Ch. 22,23,24
Week 13 (Apr. 14):  Review and test #3 (Wednesday, April 16)
(Note: afternoon classes canceled for Good Friday, April 18)
Week 14 (Apr. 21):  25, notes on P and NP
Week 15 (May 1): Review for Final
Final:  Saturday, May 3,  7:00 P.M. -  9:00 P.M.