Math 166 home page

Math 166 (THEORY OF COMPUTABILITY) Spring 2000

Important links: Schedule Homework Notes on the text Academic Integrity

Help with math: reading math definitions "if ... then" and negation proofs

Notation quiz: ps pdf Solutions: ps pdf

MEETING TIMES

Lecture: MWF 10:10 in WLH 2205
Discussion: Th 5:45 and 6:50 in WLH 2112
Office Hours:
Prof: Ed Bender email AP&M 6111 Finals Week: M 7-10 AM, Tu 11:30-2 PM
TA: Tom Langley email AP&M 2226 Hours: Wed. 11:30-1:30, Th. 4:15-5:15 Finals Week: M 1-4

TEXT: Introduction to the Theory of Computation by Sipser. Get the latest available printing, probably the second.
You are expected to read material BEFORE it is lectured on. The syllabus tells you what to expect in lecture.

I have written up some notes on the text that you may find helpful.
errata in first edition, first printing
errata in first edition, second printing (also in first printing, but not listed above)

We will quickly go over Chapter 0 (mostly review) to be sure everyone has had the background material. The course will cover

Part I (Automata and Languages) which is important in language design and pattern matching, both of which play a role in compiler design. Part I presents limited models of a computer.
Selected topics from Part II (Computability Theory) which asks "What can we expect to compute without such limitations?"
Selected topics from Part III (Complexity Theory) which asks "What can we compute in a reasonable time?"

GRADING AND EXAMS:

Academic Integrity Guidelines
Late homework is normally not accepted.
You may discuss homework, but the writeup should be your own.
Exams are closed book except for one page of notes (both sides).

15%	homework	due weekly in section (NO LATE HW)
20%	1st midterm	4th week on Fri. 4/28 in WLH 2005
25%	2nd midterm	9th week on Wed. 5/31 in WLH 2205 for Section 1 and WLH 2113 for Section 2
40%	final exam	8AM Tuesday 6/13 in WLH 2204 for Section 1 and WLH 2205 for Section 2

My old exams and solutions.
Sam Buss's web page has his quizzes (no solutions)

Q: I did poorly on the ____ "hour" exam, but I did well on everything else. Does this mess up my grade?
A: Probably not. When I assign course grades, I try to take into account the fact that someone may have had a bad day on ONE of the two "hour" exams.
Q: I did well on my exams but had trouble with homework because it takes me time to learn the material.
A: If you did the homework, but did much poorer on it than on the exams, I'll make allowances.
Q: I did well on my exams, but never bothered to do any homework. Does this mess up my grade?
A: Probably. The homework is 15% of your grade.
Q: I didn't understand some material in Chapter ___ at first, so I did poorly on that homework. What can I do?
A: The lowest homework grade is dropped.
Q: Can I be excused from homework ___ because of ___?
A: Homework is excused for reasons similar to those which allow you to get an incomplete in a course; e.g. health problems. The lowest homework (which is zero for a missing homework) is dropped.