B501 Home Page
CSCI B501
Theory of Computing, Fall 2007
Contents
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.
Professor
David
S. Wise,
Email
Office: LH 330H
Office hours: 10:00-11:00amT and 9:00-10:00amW, and by appointment.
Information about the course appears in these Web pages.
Changes will be made here and also posted to the newsgroup.
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 might
interest many people, ask it in class.
Lecture and Discussion Meeting Times
| Section | Room | Days & Time |
| 15464 | LH 019 | MW 11:15am--12:30am |
Exam and Assignment Schedule
Assignments will be due each Wednesday 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 September 24.
and in November.
The midterm test will be on October 15.
The
final (two-hour) exam
will be at 10:15am--12:15pm on December 12
Your course grade is based on three components:
- (Net of) two exams, plus a (double-weight) final exam (65%).
- Weekly assignments (25%)
- Participation (10%)
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.
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 evaluations will be available on paper (Sigh).
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