| Assigned |
Due |
Read |
Do but don't turn in |
Do and turn in |
|
|---|---|---|---|---|---|
| On your own |
You may discuss |
||||
| 1/17 |
1/24 |
1.1-4,
2.1-7, 3.1 |
2.1.33, 37,
39, 2.2.3, 6, 9, 23, 2.3.17, 27, 33, 2.4.1, 3, 7, 3.1.5, 7, 25 |
3.1.24 |
|
| 1/19 |
1/24 | 3.2 |
2.5.49, 51,
52, 63, 65, 67, 69, 2.6.7, 9, 13, 19, 29, 2.7.29, 41, 3.1.27-31, 35-37 |
3.1.38,
54 Bonus exercise: 2.7.47 |
|
| 1/21 |
1/24 | 3.2 |
3.1.42, 43 Exercise on directed graphs |
3.1.41 |
|
| 1/24 |
1/31 | 3.2 |
3.2.9, 10,
48, 50-52, 58, 59 Note there is a mistake in 52, the top 2 vertices shouldn't be adjacent. |
3.2.57 |
|
| 1/26 |
1/31 | 2.2, 2.5 |
2.2.4, 5,
7, 8, 10, 23, 2.5.64, 66, 68, 70 |
2.2.26,
31 |
|
| 1/28 |
1/31 | 2.2, 2.3,
3.2 |
2.2.11-13,
15, 17, 18, 2.3.51, 3.2.56 |
Graph
isomorphism exercise |
|
| 1/31 |
2/7 |
3.2 |
2.2.1, 2,
16, 19, 20 21, 24, 27, 28, 29 |
2.2.22 |
2.2.33 (Hint) |
| 2/2 |
2/7 |
3.2 |
3.2.47, 48,
64 |
Exercise
on paths and isomorphism |
|
| 2/4 |
2/7 |
3.2 |
3.2.30-38,
53, 65 |
3.2.47 |
|
| 2/7 |
2/14 |
3.3 |
3.2.24, 26,
28, 30-38 |
Exercise
on Euler circuits (Further hints) |
|
| 2/9 |
2/14 |
3.3 |
3.2.18, 20,
22, 39-41, 49, 54 |
3.2.41.c
and d (make sure to justify your answer) |
3.2.61 |
| 2/11 |
2/14 |
3.3 |
3.2.42, 60,
63 |
3.2.47 Bonus exercise |
|
| 2/14-18 |
|
3.3 |
No new exercises this week. Prepare for
exam. |
||
| 2/21 |
3/2 |
3.4 |
3.3.1, 3,
5, 7, 11, 23, 24 |
3.3.21, 22 |
|
| 2/23 |
3/2 |
3.4 |
3.3.15, 17,
18 |
Correction
to 3.3.23, 3.3.24 |
|
| 2/25 |
3/2 |
3.4, 3.5 |
3.3.1, 3,
9, 10, 20, 30, 31 Understand what the Maple worksheet on Dijkstra's algorithm does. |
||
| 2/28 |
3/2 |
3.5 |
3.4.11, 13,
15, 16, 21, 29, 33, 37 |
||
| 3/2 |
3/14 |
4.1 |
3.5.38, 41,
42, 44, 45, 60 |
3.4.33 |
3.4.37 |
| 3/4 |
3/14 |
4.1 |
3.5.53, 57,
58, 68 (use Dijkstra's algorithm), 73, 80. Understand the solutions to HW 5. |
||
| 3/14-18 |
|
4.1, 4.2 |
No new exercises
this week. Prepare for
exam. |
||
| 3/21 |
3/28 |
4.1, 4.2 |
4.1.14,
16-18, 20, 46 |
Exercise
(c) => (a) in Theorem 4.5 |
|
| 3/23 |
3/28 |
4.2 |
4.1.29, 31,
33-37, 45 (Hint: Remove any edge and use the inductive hypothesis on
the resulting connected components.) |
4.1.32,
but also verify your answer by reconstructing the tree from the
connection list. Do you get the original tree back? |
Exercise
(e) => (a) in Theorem 4.5 |
| 3/25 |
3/28 |
4.2 |
4.2.3, 9-13 |
No new
HW to turn in. Enjoy the weekend. |
|
| 3/28 |
4/4 |
4.2, 5.1 |
4.2.17, 19,
21, 23, 29, 31, 34, 37, 38, 40 |
4.2.32
(Make sure you justify your answer. If you are clever, you can save
yourself a lot of work by using the fact that the original Prim's
algorithm finds a minimal spanning tree.) |
4.1.45
(Hint: We proved in class without using Theorem 4.3 that removing an
edge from a tree disconnects it. So remove an edge and use the
inductive hypothesis on the connected components.) |
| 3/30 |
4/4 |
5.1, 5.2 |
4.2.42
(Hint: First prove that the graph given by Kruskal's algorithm is
connected, hence it is a spanning tree. Now use the same idea as in our
proof of Prim's algorithm to prove that its total weight must be
minimal.) 4.2.45 |
||
| 4/1 |
4/4 |
5.2 |
5.1.1, 7,
11, 15, 17-19, 21, 26, 29 5.2.7, 29, 30, 31 (Do 31 first. It's easy. Now 29 and 30 are obvious consequences if you look at Theorem 3.8) |
Bonus
exercise: Find the mistake in the April's Fool proof I gave this
morning. (If you were not in class, get someone's notes.) |
5.1.23
(deadline extended to 4/11) |
| 4/4 |
4/11 |
6.1 |
5.2.9, 17,
19 |
5.2.33 |
5.1.23 (New
hint: find a set of distinct reps and compare its elements with the
union of all sets) |
| 4/6 |
4/11 |
6.1, 6.2 |
6.1.1-6, 7,
9, 11, 31 |
||
| 4/8 |
4/11 |
6.1, 6.2 |
6.1.19, 21,
23, 33, 35 |
Find
a flow of value 0 for the network in Exercise 6.1.9, which is not 0 on
every edge. |
Let N be a
network which has no cycles. Prove that the only flow of value 0 is the
0 flow (the flow that is 0 on every edge). (Hint: Look for a longest
one among paths all of whose edges have nonzero flow.) |
| 4/11-15 |
|
6.2 |
No new exercises
this week. Prepare for
exam. |
||
| 4/20 |
4/25 |
6.3, 6.4 |
6.2.1, 3,
11, 19, 23, 25 6.3.5, 9, 11 |
6.3.12,
but find both a maximal flow and a minimal cut. 6.3.17 |
|
| 4/22 |
4/25 |
6.4, 7.1 |
6.3.7, 13,
14, 24 (We did this in class), 25 |
6.3.15
(Hint: Do (c) before (b).) |
|
| 4/25 |
5/4 |
6.4, 7.1 |
6.4.7 (the
network associated with a bipartite graph is the network we constructed
in class by orienting the edges and adding a source and a sink), 9, 11,
13 6.4.29 (Hint: proof by contradiction. This is true anytime, not only in the last iteration.) 6.4.30 (Hint: Are there any labeled vertices that are not scanned if the algorithm ends with the sink unlabeled?) |
6.4.12 |
|
| 4/27 |
5/4 |
7.1-4 |
6.4.31
(Hint: Notice that if X in V1 is
labeled then there can be no edge with nonzero slack from X to an
unlabeled vertex Y in V2
in the last iteration of the
algorithm.) 7.1.1, 3, 19, 21, 23, 29, 30 |
7.1.37
(Hint: If the first integer is k, look at C(n+k-1,n) and give it a
combinatorial interpretation.) |
6.3.15
again, but use the worksheet. |
| 4/29 |
5/4 |
7.2-4,
6 |
7.1.15-17,
25, 7.1.31 (Hint: Use C(n,k)=C(n-1,k)+C(n-1,k-1) repeatedly.), 7.1.35 (Hint: Use the Canadian lumberjack method to show C(n,k+1)-C(n,k) is nonnegative.), 7.1.38 (Hint: Differentiate x(x+1)^n once without expanding it first and once after expanding it using the Binomial Theorem. Now evaluate at x=1.), 7.2.11, 13, 15-17, 29, 31, 33, 34 |
7.1.33
(Hint: Use the result of 7.1.25 and C(n,k)=C(n,n-k).) |
|
| 5/2 |
5/4 |
7.6 |
7.2.1, 5, 7, 7.3.15, 17, 24, 25, 27, 33, 7.4.1, 7, 9, 13, 19, 23, 24, 30, 31 (Hint: Notice that if you were to pick 3 out of the numbers 1 thru 10 with repetition allowed, you could always list them in decreasing order.), 7.4.36 (Hint: You could pick the t+1-st element 0 times, 1 time, 2 times, etc.), 7.6.1, 3 |
7.6.12 (Hint: Look at how many sequences of 5 integers contain no 4s, how many contain no 7s, and how many contain no 4s and 7s. The answer is 14670, but you need to justify it.) | |