Homework |
|
HW # |
Due | Read | Do |
|---|---|---|---|
|
M 5/2 1:00-4:00 PM FN 5 |
Final exam covers these problems (click). | ||
|
|
W 4/27 |
Review for final. Midterms 2 & 3. I will soon post which HW problems the final exam covers. |
Do but don't turn in: Let f(x+1) = f(x)[f(x-1)+f(x-2)] for x>1; f(0)=1; f(1)=2, f(2)=10. Show f is computable. |
|
|
M 4/25 |
Review for final. On Monday we'll work on Midterms 1 & 2, and HWs 1-8. Look at all these problems, and whichever you feel unsure about, do them on the board on Monday. |
|
|
27 |
F 4/22 |
Wilf: Skim or read pages 183-185 if interested (they're very interesting and impressive, but we probably won't have time to cover them in this course). Read pages 186-187. |
Do these problems. |
|
26 |
W 4/20 | Wilf: Read Section 5.3 through the end of Example 5.2. | Do these problems. |
|
25 |
F 4/15 | G&J: pages 11-14. Wilf: Read or skim pages 174-177; read pages 178-179 (up to 5.3) carefully. (May skip the "pidgin-Pascal" simulation on page 177.) |
Wilf page 174: 1, 3acde, 4. Definition for #3: An Euler path (respectively, circuit) is a path (respectively, circuit) that traverses every edge exactly once. Also do these problems. |
| W 4/13 | Covers HWs 16-22, and theorems listed in their corresponding reading assignments under "be able to prove on your own." | ||
|
24 |
M 4/11 | G&J: pages 8-10. Wilf: pages 169-174. On Monday, come to class prepared with questions on the reading, and with answers to the HW problems. |
Do these problems. |
|
23 |
F 4/8 | From handouts: G&J (Garey and Johnson): pages 1-8. Wilf: pages 165-169. (Don't worry about terminology that you've never heard before, such as graph coloring, independent sets, etc. We'll talk about them in class.) |
Do these problems. You don't need to turn these in if you're sure you know how to do them. |
|
22 |
W 4/6 | Sec 7.2 pages 129-130; may skim or skip the Rice-Shapiro Theorem and
its proof. Be able to prove Theorem 2.7 (page 125), just the part for "(a) => (b)", on your own. |
Sec 7.2: 4, 7. Last part of #4: the bars above the sets denote their complements. For #8 from last HW, in part (d), what is the significance of "at least" (in italics)? |
|
21 |
M 4/4 | Sec 7.2 pages 123-128; may skim or skip Theorems 2.4 & 2.5. | Sec 7.2: 2, 5, 8, 10. For #5 & #10: see bottom of page 2 for definitions of f|A and "f-inverse of A". |
|
20 |
|
Sec 7.1. Be able to prove Theorem 1.3 on your own. | Sec 7.1: 1. Sec 6.6: 5. Also do these additional problems. |
|
19 |
M 3/28 | Read the following from Section 6.6: -- pages 112-113; -- the definition of Diophantine Predicate, and the example right after it (subsection 6.8), and Theorems 6.9 and 6.10 on page 116; -- Theorems 6.11 and 6.12 and their proofs. |
Sec 6.6: 1, 4, 6, 7bc. (For 7b, don't have to use the book's hint. For 7c, the function f(x,y) is very helpful, but may use Church's Thesis instead of the s-m-n Theorem.) |
|
18 |
F 3/25 | Casually skim Sections 6.2 (if you are familiar with group theory), 6.3, and 6.5 (if you are familiar with first-order logic). | Redo Sec 6.1: 1c-i. Also do these additional problems. |
|
17 |
W 3/23 | Section 6.1 pages 103-106. | Sec 6.1: 1c-i. Use Rice's Theorem whenever possible. Read the
paragraph at top of page 106. Why does the book mention Theorem 1.6a but
not 1.6b as a corollary to Rice's Theorem? Why does the hint in
problem 1a not suggest using Rice's Theorem? Also do these additional problems. |
| M 3/21 (postponed from W 3/9) | Covers HW 9-15 (Chapters 3-5). | ||
|
16 |
|
Section 6.1 pages 100-103. | Sec 6.1: 1ab, 2. |
|
15 |
M 3/7 | Section 5.1 page 85-86, including Theorem 1.2, but may skim its
proof. Section 5.2 (may skim the proof of Theorem 2.2). |
Sec 5.1: 1(iii) (use Church's Thesis; ignore parts (i) and (ii).). Also do these additional problems. |
|
14 |
F 3/4 | Section 4.4 (may just skim the proof of Theorem 4.3). | Sec 4.4: 1, 2. Also do these additional problems. |
|
13 |
M 2/28 | Sections 4.2 and 4.3. | Sec 4.2: 2.3. Sec 4.3: 3.2(1-4). (For #3, see page 3 for the definition of "~" .) Also do these additional problems. |
|
12 |
F 2/25 |
(Classes cancelled due to power outage)
Read Section 4.1: skim proofs of Theorems 1.2-1.4; may skip Example 1.5. Read everything else carefully, including Definitions 1.1(abc) and statements of all the theorems. |
Do these problems. |
|
11 |
F 2/18 | Read Section 3.7. | Sec 3.7: 7.2 (1, 2). Also do these additional problems. |
|
10 |
W 2/16 | Read Section 3.4. | Sec 3.4: 4.6 (1, 2). Use -- after carefully reading the
conventions on page 56. Also do these additional problems. |
|
9 |
F 2/11 | Read Sections 3.1-3.3. | Do these problems. |
| W 2/9 | Covers all of Chapters 1 & 2, except for the proofs of theorems that we skipped. | Redo -- but don't turn in -- all HW problems assigned so far (or at least the ones you're not sure about). | |
|
8 |
M 2/7 | Review for the midterm. | Sec 2.5: 5.4 (1, 2, 3). Also do these additional problems. |
|
7 |
F 2/4 | Section 2.5 (may skip proof Theorem 5.2). | Do these problems. |
|
6 |
W 2/2 | Section 2.4 pages38-41, including proofs of the theorems and corollaries. | Sec 2.4: 1-4bc. (For #2, do only the second half: show pi_1 and pi_2
are computable.) Also do these additional problems. |
|
5 |
M 1/31 | Section 2.4 up to and including proof of Corollary 4.7; but may skip proof of Theorem 4.4. | Sec 2.4: 2, 4a. In problem 2, show pi is a computable bijection, Also prove Theorem 4.5 and Corollaries 4.6 and 4.7. They are proved in the book. You need to be able to prove them with the book closed. |
|
4 |
F 1/28 | Sections 2.1, 2.2, 2.3 (may skip proofs of theorems). | Sec 2.3: 3.4 (1, 2, 3). For #1b, may assume f(x,y)=x+y is computable (as in Example 3.3). For #3, may assume "x=y" is decidable. Also do these additional problems. |
|
3 |
W 1/26 | Section 1.4, skim 1.5. | Sec 1.4: 4.3. Sec 1.5: 5.2(1); use the coding convention discussed in class for negative integers. |
|
2 |
M 1/24 | Section 1.3. | Sec 1.3: 1-4. |
|
1 |
F 1/21 | Sections 1.1, 1.2. | Sec 1.2: 2.2, 2.3. Also, read and play with URM Simulator. |