Math 188 Schedule and Homework
Tentative
Schedule. Check weekly for changes.
|
wk |
date |
Monday |
Wednesday |
Friday |
|
1 |
4/03 |
A.1-3 |
A.4-7 |
A.8 |
|
2 |
4/10 |
1.1-2 |
1.3, 1.4.1 |
1.4.2 |
|
3 |
4/17 |
1.4.2, 2.1-2 |
2.2-4 |
2.7-8, B.1 |
|
4 |
4/24 |
B.2 |
Exam |
B.3-4 |
|
5 |
5/01 |
B.4, 3.1 |
3.2 |
3.2-3, 4.1 |
|
6 |
5/08 |
4.1 |
4.1-2 |
4.2, 4.4 |
|
7 |
5/15 |
5.1-2 |
5.2-3 |
5.4 |
|
8 |
5/22 |
5.4, 5.7 |
7.1-3 |
Exam |
|
9 |
5/29 |
Holiday |
7.8.1-3 |
8.1 |
|
10 |
6/05 |
8.5.1 |
8.5.1-3 |
Review |
Math 188 Homework (due in section) page up for schedule
Late homework will normally
not be accepted.
See policy on discussing
and writing up homework.
Solutions will be made available at soft reserves.
Old homework
Due 6/1:
Ch.7: 2, 3, 9,12
Last
HW: (not to be handed in) Ch. 7: 38,
40; Ch. 8: 1, 19, 20
** Hint on 7.38: Use n bins
Old
Homework
Due 4/6: Appendix
A: 1(a,c,f), 3, 5, 6(a), 9, 11, 15, 16, 24, 28, 29, 30, 37, 40(give
a reason) Yes, there is probability in the homework
and I haven't covered it in lecture yet; however, this is supposed
to be review. The other assignments will not be due before
the material is covered.
Due 4/13: Ch.1:
3*, 8, 10(#3), 13
** No. 3: Remember that subsets are combinations, which are counted
on page 449.
Due 4/20: Ch1: 15, 19*,
20(1,2)["establish" means "prove"], 22;
Ch.2: 2, 6*, 10*, 14, 16(don't solve recursion)
** No.19: You should put all 16 items into complexity categories. Remember,
f (n) and g(n)
are in the same category if they grow at the same rate.
You may find n! = Theta (n^{1/2} (n/e)^n)
useful.
** No. 6: Suppose that n is a power of 3 and the list is
divided into 3 equal parts. To choose a part, look at the
entries in position n/3 and (possibly) 2n/3. Unlike
the binary search algorithm (but like the incorrect analysis in
the text), do not discard the entries that have been looked at
when creating the new lists.
** No. 10: If necessary, you may assume that n is a power
of 2.
Exam
4/26:
On Appendix A and Sections 1.1 through 2.4 (including 2.4). In Center 113.
Closed book. No notes allowed. You may bring
a calculator. Blue books are NOT needed.
My
old exams and solutions
Due
4/27: Ch. 2: 38(don't solve recursion), 40(a);
Appx. B: 1(a,d,g), 9, 10, 12(a,b), 19(a) Just
do #9 and #10 for problem 1(a-h).
Due
5/4: Appx. B: 24; Ch.3: 2, 5*.
* Do not do all of problem 3.5: Just give
(a) The contents of the D and P
arrays after the loop on k has be executed for k=1 and
(b) The contents of the D array
at the end of the algorithm.
Due 5/11:
Ch.3: 10, 33; Ch.4: 3, 8, 9.
In the graph for Chapter 4, Problem 2:
(a) List the edges in the order Prim's algorithm
adds them to build a minimum spanning tree.
(b) List the edges in the order Kruskal's algorithm
adds them to build a minimum spanning tree.
Due
5/18: Ch 4: 14, 15, 33; Ch.5: 3, 7
** In 5.3, show that 155 is the number of times "visit v"
is executed in the algorithm on page 178.
Due
5/25: Ch.5: 13, 35 (This means other than in the chapter--not
just the assigned sections.)
Exam 5/26: On material covered in Appendix B and Chapters
3-5. In
Center 113.
One page of note (both sides). You may bring a calculator.
Blue books are NOT needed.
My
old exams and solutions