B501 Home Page

CSCI B501
Theory of Computing, Spring 2009

Contents

General Information

B501 is a conventional graduate course in foundations. The ordinary prerequisite is C241; an alternative is substantial mathematics---particularly algebra or logic.

The plan for the semester is to to review induction, to cover regular languages (and lexers), context-free languages (and parsers), Turing machines and linear-bounded automata (and Turing-recognizable and context-sensiteve languages). Then decidability and undecidability and results from reducibility. Finally time and space complexity classes. We will be using Introduction to the Theory of Computation [2nd edition] by Michael Sipser (Thompson, 2006). The content is a full plate, corresponding to Chapters 1--8.2 in the textbook.

There will not be much use of computing in the class; most of the exercises are pencil and paper. There will be some opportunity for computing, and we might pursue that, too.

Instructors

Professor

David S. Wise, Email
Office: LH 330H
Office hours:

Associate Instructor

Zhou Li, Email
Office: LH 330A (855-9109).
Department Mailbox Number 80.
Office hours:

Communication

Information about the course appears in these Web pages.

Use judgement in how your raise questions. If you have a personal question, e.g. with a grade you received, talk to an instructor privately. If you have a question that would interest many people, ask it in class. (Email inquiries should require only very short answers---suitable to the medium.)

Schedule

Lecture and Discussion Meeting Times

Section Room Days & Time
29355 LH 115 MW 11:00am--12:15pm??

Exam and Assignment Schedule

Assignments will be due each Monday in class. Sometimes they may be called in at the beginning of class, sometimes at the end. In the latter case, you may mark them during class----but only in a different color ink or pencil from the rest of the work. Quiz on Feburary 9. The midterm test will be on March 2. The final (two-hour) exam will be at 5:00--7:00pm on May 6.

Grading

Your course grade is based on three components: The percentages represent the value in the course grade computation.

Quizzes and Tests

The quizzes and tests throughout the semester, above will be given during the regular lecture meeting time in the regular classroom.

Weekly Assignments

You may do the assignments using verbal resources from anyone, including fellow class members, but as pen hits paper the work is to be your own. Discussion is encouraged, but copying is forbidden. Since there are so many weeks for these assignments, assignments will not be accepted after the class in which they are announced as due, except for extensions granted to the entire class.

Participation

Participation in the class can take many forms: attendance at lectures and discussions, asking and answering questions posed in class and on the newsgroup, and participating in group activities during lecture.

Course Content

Course Evaluations

Course evaluations will be available on paper (Sigh).

Useful Links

Miscellaneous

Incompletes

Incompletes are given only because of an unforeseen emergency that is preceded by diligent work, not for a pattern of weak performance. No student will be allowed to do extra work to raise her (GSBCF) final grade or to make up missing work.

Academic Integrity

By all means talk to one another about the problems, the course, the weather! Graduate school is a shared experience, and you can learn as effectively from one another as you can in lecture. But when you sign a paper indicating that the work is your own, make sure that the written work is your own. That is, your ownership begins when pen hits paper---or when fingers hit mice. All written work is to be prepared independently. Read the Computer Science Department's Statement on Academic Integrity to be sure you understand the rules under which CS courses operate.
David S. Wise