CS481 - Intro to Theory of Computing - Fall 2001

14 Dec: Notes on Final.

The Final is Tues, Dec. 18, 12:00-2:30, PH403. Here is a list of topics to be covered.

5 Nov: Prelim 2 in class Wednesday.

Covers context-free languages up to but not including the Parikh Theorem. As usual, open book and notes.

29 Oct: DPDA Complementation

A revised construction for complementing a DPDA.

14 Sept: Proving L(M) = L

Here is some mail discussion and examples of what is required.

14 Sept: HW1 correction

In problem (2), assume L is an infinite regular language. The results do not hold for finite languages.

7 Sept: correction to HW0 correction

The assumption that the alphabet contains at least two symbols is required for question 1(d); you do not need it for question 2. In fact, I don't care much about empty or single-letter alphabets, so henceforth you may assume any alphabet has at least two symbols unless you are explicitly told otherwise.

6 Sept: corrections to HW0

There are a couple of typos/bugs in HW0.

(Ques 2) Assume the alphabet contains at least two symbols. This problem does not work for empty or single-letter alphabets.
(Ques 3c) Should read "does the answer to part (b) change"

Homework Assignments

3 Sept: Homework 0

10 Sept: Homework 1

17 Sept: Homework 2

26 Sept: Homework 3

10 Oct: Homework 4

17 Oct: Homework 5

24 Oct: Homework 6

14 Nov: Homework 7

28 Nov: Homework 8

Homework Solutions

Homework 0: q1: avg 9.2 std 1.5; q2: avg 8.1 std 2.8; q3: avg 6.7 std 2.4
Homework 1: q1: avg 9.1 std 1.0; q2: avg 6.5 std 2.9; q3: avg 4.3 std 3.9
Homework 4: q1: avg 8.8 std 1.9; q2: avg 6.9 std 2.4; q3: avg 7.7 std 2.7
Homework 5: q1: avg 9.1 std 1.3; q2: avg 8.2 std 1.4; q3: avg 8.2 std 2.3
Homework 6: q1: avg 8.5 std 2.3; q2: avg 9.1 std 1.8; q3: avg 9.0 std 0.8
Homework 7: q1: avg 8.4 std 1.3; q2: avg 9.0 std 0.9; q3: avg 9.4 std 1.2
Homework 8: q1: avg 9.7 std 1.1; q2: avg 9.5 std 0.9; q3: avg 8.6 std 1.6
Prelim 1: q1: avg 20/30 std 5.7; q2: avg 5.2/20 std 6.1; q3: avg 17.8/30 std 7.2
Prelim 2: q1: avg 20.3/30 std 6.2; q2: avg 15.5/25 std 5.7; q4: avg 8.7/20 std 6.7; q3: avg 16.0/25 std 6.8
Final: mean 88.4/143

Staff with Office Hours

Instructor:

Alan Demers (ademers@cs.cornell.edu): Mon 1:00-2:00; Wed, Fri 10:00-11:00 Upson 4115

Teaching Assistants:

Anirban Dasgupta (adg@cs.cornell.edu): Thurs 1:30-3:30 Upson 328D
Allen Wang (wangal@cs.cornell.edu): Tues 11:40-1:30 Upson 328C
Misha Zatsman (mz36@cornell.edu): Mon, Wed 11:15-12:05 Upson 328C