(4/20) Review/cram session, May 1, 5-8pm, ECCR 1B55.
(4/16) Due 4/29 (40): Reading: 12.5. Exercises: 12.4.6, 12.4.16, 12.4.24.
(4/16) Due 4/27 (39): Reading: 12.4 and Sections 2 & 3 of these notes. Exercises: 12.3.8, 12.3.46, 12.3.50.
(4/16) Due 4/24 (38): Reading: 12.3 and Section 1 of these notes. Exercises: 12.2.6, 12.2.24, convert the prefix code tree of Example 10.2.5 to a Mealy machine to decompress a file constructed with that prefix code.
(4/3) Due 4/10 (32): Reading: 10.2. Exercises: Review Set 3.
(4/2) Due 4/8 (31): Reading: 10.1. Exercises: 9.8.6, 9.8.8, 9.8.12 (just answer for 6 and 8), 9.8.36. This problem set is purposely short to provide you with more time to work on Review Set 3, due 4/10.
(4/1) Alternative (short) explanation of shortest paths.
(3/31) Due 4/6 (30): Reading: 9.8. Exercises: 9.7.16, 9.7.18, 9.7.32 (hints: (1) in 18 and 32, let ei and vi be the number of edges and vertices, respectively, in the subgraphs; (2) in 32, apply corollary 9.7.1 to the k planar subgraphs and sum the resulting inequalities).
(3/31) Due 4/3 (29): Reading: 9.7. Exercises: 9.6.14, 9.6.16, 9.6.26 (just state the minimum-weight Hamilton circuit), and this.
(3/3) Due 3/6 (20): Reading: 8.2-3. Exercises: 8.1.6 (a-d), 8.1.56 (hint: First prove that R o (S o T) = (R o S) o T; then prove that for all positive n, Rn o R = R o Rn; then prove the main theorem. Of course, there may be other ways.)
(2/11) Due 2/18 (15): Reading: 3.7. Exercises: 3.5.32, 3.6.30 (hint: look at solution to 3.6.29), 3.6.38, 3.6.40, 3.6.42.
(2/11) Due 2/16 (14): Reading: 3.6. Exercises: 3.4.12, 3.4.24, 3.4.32 (a), 3.5.6 (hint: look at prime factors), 3.5.34 (hint: you might write a program for this one).
(2/5) Due 2/13 (13): Reading: 3.4-5. Exercises: Review Set 1, which you can start as early as today --- we have covered all the material in it.
(2/5) Due 2/11 (12): Reading: Section 4.4 of the first set of notes, Section 5 of the second set of notes. Exercises: 3.2.4, 3.2.36 (prove your claim), 3.2.50, 3.3.12, 3.3.18.
(1/27) Due 2/2 (8): Reading: Section 4.3 of the notes, Sections 1.6, 2.1-2 of the textbook. Exercises: 4.5, 4.7, 4.8 from the notes.
(1/27) Change to exercises due 1/30 from what was originally posted: 4.3, 4.6, 4.9. Well-founded induction is not necessary for these problems; you should be able to do them all based on Wednesday's lecture.
(1/27) I have made changes to Section 4 of the predicate logic notes; please refresh your local copy.
(1/20) (updated) Due 1/30 (7): Reading: Section 4.2 of the notes. Exercises: 4.3, 4.6, 4.9 (well-founded induction is not necessary for these problems).
(1/20) Due 1/28 (6): Reading: Section 4.1 of the notes. Exercises: 3.2 (3, 5, 7, 8), 4.1.
(1/20) Due 1/26 (5): Reading: Section 3 of the notes. Exercises: from first set of notes: 3.2 (9); from new notes: 2.4, 3.1, 3.2 (2).
(1/20) Due 1/23 (4): Reading: Sections 1-2 of these notes. Exercises: from first set of notes: 3.3 (1, 3, 4); from new notes: 2.2, 2.3.
(1/12) Due 1/21 (3): Reading: Section 3 of the notes. Exercises: 2.3 (parts 3, 4), 3.1, and 3.2 (parts 3, 4) in the notes.
(1/12) Due 1/16 (2): Reading: Section 2 of the notes. Exercises: 1.3 (parts 3, 4) and 2.3 (parts 1, 2) in the notes.
(1/12) Due 1/14 (1): Reading: Section 1 of the notes. Exercises: 1.1 (parts 1, 3) and 1.2 in the notes.
(1/12) Wow. Total screw-up on my part; see my email for details.
(1/10) Notes on predicate logic. These will be the main text on the topic; Rosen, Ch. 1 is supplementary.
(1/10) Through a mistake on my part, the Rosen book has not yet arrived at the bookstore. However, we will use my notes the first few weeks, anyway; the book should arrive by the time we need it.
(1/8) Notes on propositional logic. These will be the main text on the topic; Rosen, Ch. 1 is supplementary.
Homework: A reading assignment and corresponding short problem set is due at every lecture, reviewing previous topics and introducing that day's lecture material.
Exams: There will be an in-class midterm (March 2) and final (Saturday, May 2, 1:30-4:00). Contact me at least two weeks in advance if you need to schedule an alternate time to take either one.
Grading: homework - 25%, midterm - 25%, final - 50%