Misc. Announcements
- NEW (April
15) Grades (gpa) for #3 can be found here.
UNOFFICIAL course grades (letter) can be found here.
- (April
12) Grades (gpa) for #2 can be found here.
(Most of the difficulty that students encountered was with some of the
reductions and the [two] Ackermann problems.)
- (April 5)
Problem
#3 (Set #3) was originally stated in a confusing manner. See the
corrected version below.
- Problem
#7 (Solutions, Set #2) is now corrected. Alexandra caught the error
(thanks).
- Assignment #2 is due any
time on
Thursday, March 23, 2006 (in the course box). I'll collect on
Friday, and then post the solutions.
- Students
are asking me for a hint for problem #(5) in problem set #2. Well, one,
do not try a
dirrect induction proof of a statement that is true "a.e.": You don't
know where the basis is. Two, prove as a lemma, by induction on x or
otherwise, that A_x(2)>x+1 for all x (by underscore I mean
subscript). Then rather than proving A_x(2)>A_n(x) a.e. with respect
to x, prove A_{x+1}(2)>A_n(x) a.e. instead (is this enough? Why?)
- (March
12) A newer version of the Kleene Normal Form notes is
posted. It fixes a typo in the composition figure, and also
restores broken (internal to the document) references.
- (March 9). The
due date for Problem Set #2 is March 23, by 4pm, in the course box.
- (Feb 24)
A newer version of the Kleene Normal Form notes is now available.
It now deserves to be the only version posted here.
- Some
typos in the "Revised Notes" about the Kleene Normal Form have
been attended to (in the figures).
- New
version of the Kleene Normal Form notes is now posted (see under
Lecture
Notes below).
- Notes on
the Ackermann function are now posted (see under Lecture
Notes below).
- Assignment number 1 is due Feb 20,
2006, by 4pm, in the course
box. All assignments are
due by 4pm on the date they are due in the course box. This is
located in CSEB, main Nort/South corridor opposite of the Prism Lab,
and is labelled by the course number and my name.
- Notes on Loop Programs
(see under Lecture
Notes below)
Office Hours: Tuesday and Thursday, 4:00pm - 5:15pm (Location: Room 2051 CSB)
Misc. Lecture Notes.
- Revised
Again (Feb 24)
Notes on the Kleene Normal Form. Download
(PDF)
- Notes on the Ackermann function. Download (PDF)
- A brief
note on Loop Programs. Download (PDF)
- On
Turing Machines, briefly and informally (from CSE2001 notes): PART 1: PDF, PS
and PART 2: PDF, PS.
- Gödel's 1st
Incompleteness Theorem: DVI,
PDF, PS.
- Why mathematicians should not lose
any sleep over automatic theorem provers. Download DVI , PDF, PS
.
Problem Sets
The text of all answers is
expected to be typed.
(Some students may wish to type/word process even diagrams and
symbols! However this is not
required.)
- Problem Set #1:
Posted January 23, 2006. Due: February
20, 2006. Download (PDF). NOTE. I have dropped problem 21.
- Problem Set #2:
Posted February 26, 2006. Due: March 23, 2006. Download
(PDF).
- Problem Set #3:
Posted March 19, 2006. Due: April
6, 2006. Download (PDF).
Sample Solutions
- Problem Set #1:
Posted February 22, 2006. Download
(PDF).
- Problem Set #2:
Posted March 24, 2006. Download
(PDF). Corrected (Problem #7; on April 2).
- Problem Set #3:
Posted April 11, 2006. Download
(PDF).
Return to courses main page .
Return to my "general" home
page .
Last changed: April 15, 2006.