Instructor: Martha O'Kennon, Palenske 305.  
Office hours:  MWF 10:10 - 11:00, or by appointment (make appointments by e-mail)
Office phone: 0300 (but do not count on voice mail, as it is flaky and I don't check it every day)
E-mail:  mokennon@alpha.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 339 (discrete math).  Familiarity with programming constructs such as recursion and looping and basic algorithm analysis, such as are learned in Math 273.

About this course.  This will be the first time this course is offered at Albion.  It deals with the theoretical underpinnings of computer science, and has direct applications to such studies as compiler design and algorithmic analysis.  (By the way, I use many of its ideas in my studies in applied linguistics.)  We will study several classes of computer languages, and the corresponding classes of theoretical machines that recognize the language (either accepts an input string as grammatically correct or accepts the string and produces 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.

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 will be one or more programming projects assigned.  (Some of these may be group projects.) 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, but they are not to be discussed with anyone but me.  At the end of the term, I will compute a weighted average, and final grades are assigned according to the following table.

4.0         94% or above, with some extra credit
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%

Tentative Syllabus:

Week 1  (Begins January 11): Chapters 1 - 4
Week 2  (Begins Jan. 19 - Note: Monday January 18 is Martin Luther King Holiday):
         Ch. 5, 6 (Also note: Tuesday, Jan. 19 is the last day to add or drop a class)
Week 3 (Jan. 25):  Ch. 7 -8(Note: Monday, Jan. 25 is the last day to register for
          credit/no credit)
Week 4 (Feb. 1):  Ch. 8. 9, Review for test #1
Week 5 (Feb. 8):  Test #1 (Monday, Feb. 8), Ch.10,11
Week 6 (Feb. 15):  Ch. 12,13
Week 7 (Feb. 22):  Ch. 13, 15
Week 8 (Mar. 1): Ch. 15, 16
(Note:  Spring Break begins at 5:00 pm on Friday, March 5)
(Note: Midsemester is March 8)
Week 9 (Mar. 15):  Ch. 17.18, Review
Week 10 (Mar. 22):  Test #2 (Monday, March 22), Ch. 19, 20
(Note: last day to drop with grade of "W" is Monday, March 22)
(Note: Academic Advising March 22 - March 30)
Week 11 (Mar. 29):  Ch. 20, 21(Note: afternoon classes canceled for Good Friday, April 2)
Week 12 (Apr. 5):  Ch. 22,23
Week 13 (Apr. 12):  Ch. 24, Review and test #3 (Friday, April 16)
Week 14 (Apr. 19):  25, notes on P and NP
Week 15 (Apr. 26): Notes on NP-completeness, Review for Final
(Note: Thursday, April 29 is the last day of classes)

Final Exams begin on Saturday, May 1.