Homework |
|
HW # |
Due | Read | Do |
|---|---|---|---|
| F 12/18 1:00-4:00 pm Fowler 307 |
The final exam will cover all homeworks, with a bit of emphasis on HWs
20-23. Office hours during exam week: Wed 11:30-3:30. Fri 9:00-12:00 in Fowler 113 (I'll be giving an exam there, but can come out and talk with you). Tues 11:00-1:00, but my Math 212 students will get priority because they have an exam Wed morning. |
||
|
23 |
M 12/7 | Nothing | Do these problems. |
|
22 |
F 12/4 | Read about the Hopfield Network (in
preparation for Friday's lesson) www.phy.syr.edu/courses www.phy.syr.edu/courses www.phy.syr.edu/courses |
Nothing. |
|
21 |
W 12/2 | Do these problems. | |
|
20 |
M 11/30 |
Read "Reducibility" : Wilf p. 171, and top of 172. | Do these problems. |
| M 11/23 | Will cover HW 13-19. | ||
|
19 |
W 11/18 | Read Wilf p. 169-171. |
Wilf p. 174, Excercies 5.1.1: 4a-c. For 4b (from Wikipedia): "a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence." Also do these additional problems. |
|
18 |
M 11/16 | Read Wilf (2nd Edition -- class handout) p. 165-169 up to and
including "What is the class P?" Also read Gary and Johnson (class handout) p. 1-14; don't worry about the technical details; just do a light reading to get the big picture. |
Wilf p. 174, Excercies 5.1.1: 1, 3cd. |
|
17 |
F 11/13 | Read p. 1-7 of the first edition of Wilf's book, (original source) | Do these problems. |
|
|
http://www.bitstorm.org/gameoflife/ http://en.wikipedia.org/wiki/Conway%27s_Game_of_Life http://plus.maths.org/issue20/features/conway/index.html YouTube: Wolfram -- A new kind of science |
||
|
16 |
M 11/9 | Sec 6.1 (p. 106): 1de. | |
|
15 |
F 11/6 | Read Sec 6.1 p. 100-102. |
Sec 6.1 (p. 106): 1c. Do these problems. |
|
14 |
M 11/2 | Do these problems. | |
| F 10/30 | Will cover HWs 7-12. Here is Mid2 of 2006. Our exam will be different (but somewhat similar). |
||
|
13 |
W 10/28 | Review for the midterm. | Do these problems. |
|
12 |
M 10/26 | Sections 4.2 and 4.3. |
Sec 4.2 (p. 77): Exercise 2.3. Sec 4.3 (p. 80): 2-4. |
|
11 |
W 10/21 | 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. |
|
10 |
F 10/16 | Read Section 3.7. |
Sec 3.7 (p. 71): 1, 2. Also do these additional problems. |
|
9 |
M 10/12 |
Read Sections 3.4. (p. 52-56). |
Sec 3.4 (p. 57): 1, 2. Read the conventions on p. 56 carefully before
doing the problems. Also do these additional problems. |
|
8 |
W 10/7 | Read Sections 3.1-3.3. | Do these problems. |
|
7 |
M 10/5 | Section 2.5 (may skip proof Theorem 5.2). |
Sec 2.5: 1, 3. Also do these additional problems. |
| W 9/30 | The exam will cover HWs 1-6.2, and proofs of Theorem 4.5(a-k) and
Corollaries 4.6 and 4.7 (p. 36-38). Here is Mid1 of 2006. Our exam will be different (but somewhat similar). |
||
|
6.2 |
F 9/25 | 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 exactly one prime number divides x. Also do these additional problems. |
|
6.1 |
M 9/21 | Read and learn the proofs of Theorem 4.5(a-k) and Corollaries 4.6 and 4.7. You need to eventually be able to prove them with the book closed. |
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. |
|
6 |
F 9/18 | Section 2.4 up to and including proof of Corollary 4.7; but may skip proof of Theorem 4.4. |
Sec 2.4: 4a. In Problem 4a, do not write a program; instead use Theorem 4.5; hint: use parts (f) or (g), and part (l) of the theorem. Optional extra problems |
|
5 |
W 9/16 | Read Theorem 3.1 on p. 29 (skip the proof). Read all of page 31, including Theorem 3.2 and its proof. |
Sec 2.3: 3.4 1b, 2, 3. Do all these problems without writing any
programs. For #1b, you may assume f(x,y)=x+y is computable (as in Example 3.3). For #3, you may assume the predicate "x=y" is decidable. |
|
4 |
M 9/14 | Just skim Sec 1.5. Sections 2.1-2.2: Read p. 25 and top of p. 26 carefully; then just skim the rest of Sec 2.2. |
Sec 1.5: 5.2(1); use the coding convention discussed in class for
negative integers. Sec 2.3: Exercise 3.4: 1a. Use Lemma 1.1 (p. 25), together with the theorem we learned in class today for composition of computable functions. Also do these additional problems. |
|
3 |
F 9/11 | Sec 1.4. | Sec 1.4: 4.3. |
|
2 |
W 9/9 | Sec 1.3. | Sec 1.3 (p. 21-22): 1-4. Hint for #3: Use induction on the number of instructions. |
|
1 |
F 9/4 | Sections 1.1, 1.2. Here are pages 1-16, in case you don't have the book yet (get one ASAP, please; I'm not allowed to keep posting more pages). |
Sec 1.2: 2.2, 2.3. Also, read and play with URM Simulator. |