Homework |
|
HW # |
Due | Read | Do |
|---|---|---|---|
| F 12/8 | Covers all HW sets, with some emphasis on the recent material (HWs
18-21). Here's last year's final, just for practice. |
Review the following especially: Midterms 1, 2, 3, and last year's final; From Extra Problems: From the book's exercises: |
|
|
|
Just for fun: http://cs.smu.ca/~dawson/abacus.html | ||
|
21 |
M 12/4 | Do these problems. | |
|
20 |
M 12/4 |
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-4. Definitions for #3. Also do these problems. (The broken links to "Primes is in P" in these extra problems are now fixed.) |
|
19 |
M 11/20 | 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. |
| F 11/17 | Covers Homeworks 13.5-17. For practice: last year's Mid 3 (ignore problems 4, 5, 7). |
||
|
18 |
F 11/10 | From handouts: G&J (Garey and Johnson): pages 1-8. Wilf: pages 165-169. (Don't worry about terminology that you've never seen before, such as "graph coloring", "independent sets", etc. We'll talk about them in class. Just read on and try to understand what you can.) Here's an online copy of the first edition of Wilf's book, which can also be downloaded from its original source. |
Do these problems. |
|
17 |
W 11/8 |
Section 6.6 pages 112-114. | Sec 6.6 (page 119): 1, 4, 7. (For 7b, you don't have to use the book's hint. For 7c, the function f(x,y) is very helpful, but you may use Church's Thesis instead of the s-m-n Theorem.) |
|
16 |
F 11/3 |
Section 6.1 pages 100-103. | Sec 6.1: 1a-e. Also write up a complete and detailed proof that the Busy Beaver function B(n) is not computable. You'll need to take care of the two "gaps" mentioned in class. Hint for Sec 6.1, 1a: Read the proof of Theorem 1.1 on page 101. If still stuck, here's Hint #2: Assume, towards contradiction, that it is decidable; then use this assumption to construct a computable function f whose range is different from Ex for every x. Also do these additional problems. |
|
15 |
F 10/27 | Sec 5.1: Just skim page 85 and the top half of page 86. | Do these problems. |
|
14 |
W 10/25 | Optional: skim section 4.4. | Do these problems. |
|
13.5 |
M 10/23 | Sections 4.2 and 4.3. | Sec 4.2: Exercise 2.3 (p. 77). Sec 4.3: 1-4. |
| F 10/20 | Covers Homeworks 7-13. Not on Mid2 (these problems are important, but won't be on Mid2): HW7: Q3. HW8: IIa, IVa. HW10: 1, 2, I. HW11: 3. HW12: II, III. Note: the Roman numerals (and "Q3") refer to the "additional problems"; the decimal numerals refer to book's problems. |
||
|
13 |
W 10/18 | Review for Mid 2. Can test yourself with last year's Mid 2 (but ignore problems 4 and 5 for now). | Do these problems. |
|
12 |
F 10/13 |
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 |
M 10/9 |
Read Section 3.7. | Sec 3.7: 1, 2, 3. Also do these additional problems. |
|
10 |
W 10/4 | Read Section 3.4. | Sec 3.4: 4.6 (1, 2). Carefully read the conventions on page 56. Also do these additional problems. |
|
9 |
F 9/29 | Read Sections 3.1-3.3. | Do these problems. |
|
8 |
W 9/27 | Sec 2.5: 1, 3. Also do these additional problems. |
|
|
7 |
M 9/25 | Section 2.5 (may skip proof Theorem 5.2). | Do these problems. |
| F 9/22 | Covers Homeworks 1-6. | To prepare for the exam, see if you can do all previous HW problems without looking at your solutions. Once you believe you're ready, try Spring 2005 Mid 1 as a practice test. | |
|
6 |
Read Section 2.4 pages 39-41. | Sec 2.4: 1b-f, 2, 4bc. In #1b, [x] denotes the floor function (i.e., round down; e.g., [5.8] = 5). For #2, do only the second half: show pi_1 and pi_2 are computable. Hint for #4b: x is a power of a prime iff only one prime number divides x. Also do these additional problems. |
|
|
5.5 |
F 9/15 | Read page 38 up to Corollary 4.11. | Sec 2.4: 1a, 2, 3. Hint for 1a: use induction on n. For problem 2, just show pi is computable. Do not write a URM program; you may only use the three basic functions, the constant functions (f(x) = m, where m is a fixed natural number), the functions in Theorem 4.5, and the Substitution and Recursion Theorems. Note that Theorem 4.5 does not show that "x-1" is computable -- it only shows that cut-off subtraction ("minus-dot") is computable. Also do these additional problems. |
|
5 |
W 9/13 | 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 bijection, and show it is computable; but don't show pi_1 and pi_2 are computable. (See page 2 for definition of bijection.) In Problem 4a, do not write a program; instead use Theorem 4.5. Also, read and learn the proofs of Theorem 4.5 and Corollaries 4.6 and 4.7. You need to eventually be able to prove them with the book closed. |
|
4 |
M 9/11 | Read Sections 2.1-2.3. Just skim pages 26-28. May skip proof of the Substitution Theorem (3.1). May also skip Theorem 3.2. | 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 |
F 9/8 | Read 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 |
W 9/6 | Section 1.3. | Sec 1.3 (p. 21-22): 1-4. |
|
1 |
F 9/1 | Sections 1.1, 1.2. | Sec 1.2: 2.2, 2.3. Also, read and play with URM Simulator. |