CSI 350 - Theory of Computation
Instructor: Dr. Shaun D. Ramsey 
Email: sramsey2@washcoll.edu
Website: http://shaunramsey.com/350
Phone: (410)810-7485 
Office: DUNN N102

Text: Theory of Computation by Goddard

Office Hours: Tu/Th 12:00, W 2:30

Tentative Exam Dates: 2/18 and 4/3. The final in its given slot.

Grade Breakdown: 2 Exams 25% each, Final Exam: 35%, 
      Quizzes, Classwork, Homework 15%


Overview: Theory of computation is the study in the fundamentals of
computer science. A computer scientist should understand the notions
of tractable, intractable and complexity before attempting to tackle
any problem. By first examining simple languages and building up to
higher and more complex languages, we develop a method of
understanding complexity.

Advising: Knowledge of discrete mathematics, implications, sets and
proof techniques will be valuable in this course.

Exams: The final exam will be administered during its scheduled slot
during final exam week. An absence on the day of the exam will result
in a grade of 0. Except in cases of very extreme emergency, exams must
be taken on the day the exam is given.  Before a make-up test is
scheduled, documentation of the extreme emergency must be
given. Make-up exams for tests missed due to an extreme emergency will
be arranged for a time that is mutually convenient for the student and
Dr. Ramsey.

Attendance: Attendance is mandatory in this course. On your sixth
absence, you automatically fail the course. As a matter of courtesy,
you are expected to notify Dr. Ramsey before class describing the
reason of your absence. You must be present on the day of an exam/quiz
or you will receive a 0.  There is no distinction between excused and
unexcused absences. It is quite likely that I will email you to
discuss the reasons you have missed the class, but it is ultimately
your duty to keep track of your absences and to contact me. Missing a
class may result in missed classwork and/or quizzes.  There are no
make-up quizzes or classwork. It is your responsibility to obtain
assigned homework, announcements and class notes from a classmate.
Coming late to class will also count against you. In this case, every
two late arrivals count as an absence. Thus you fail the course with
12 lates or 6 absences or some combination.

Grading: Late homework (and programming that does not compile) will
receive a 0. Homework is due by the beginning of class on the day it
is due. If you miss an assignment, you should always make up the work
for consideration, review and mark up.

Academic Honesty: You are always subject to the Honor Code of
Washington College. Always sign the honor code on materials that you
hand in to me. All work must be your own.

Accommodations: If you have an accommodation that has been reported to
the college, please let me know as soon as possible so I can work to
meet your accommodation. To receive your accommodation, you must notify
me at least two weeks prior to the requirement.


General Schedule and Readings:
Week 1: Finite State Machines, Regular Languages and REs (Chapter 1-2)
Week 2: Nondeterminism, Conversions (Chapter 3 and external)
Week 3: Pumping Lemma (Ch 4)
Week 4: Properties and Applications (Chapter 4-5)
Week 5: Review, Exam
Week 6: Stack, PDAs, Context Free Languages (Chapter 6 and 7)
Week 7: Generation, Normal Forms, Context Sensitivity (Chapter 8)
Week 8: Pumping Lemma (Ch 9)
Week 9: Properties (Chapter 9)
Week 10: Review, Exam
Week 11: Turing Machines, Decidability (Chapter 11, 12 and 13)
Week 12: Countability, Halting Problem (Chapter 14)
Week 13: Reducibility and Rice's Theorem (Chapter 16)
Week 14: Complexities, time (P vs NP), And Space (Chapter 17-18)
Week 15: NP-complete and Review