| 1 |
Aug 24 |
1.1, 1.2 |
Read the course syllabus and sections 1.1 and 1.2.
An ice-cream shop has 7 flavors. John visits the ice-cream shop 3 days in a row, ordering one scoop of ice-cream each day.
- How many ways can John order ice-cream?
- How many ways can John order ice-cream if he orders the same flavor on the first and third days?
- How many ways can John order ice-cream if he orders different flavors on the first and third days?
- What is the relationship between your answers? Explain.
1.1 and 1.2: 1--7 (odd), 10, 12, 14(a,b), 15, 20, 23
|
| 2 |
Aug 31 |
1.3, 1.4 |
Read sections 1.3 and 1.4.
1.3: 1, 2, 3(a), 4, 7--13(odd), 15(a), 16(a,d,e), 17(a,b,c,d), 20, 23, 25(a,c,e), 27(a,c,e), 30, 32.
1.4: 1--5 (odd), 7(a,f), 12(a), 13, 15
|
| 3 |
Sep 7 |
1.4, 3.1 |
Read sections 1.4 and 3.1.
1.4: 1--5 (odd), 7(a,f), 12(a), 13, 15
3.1: 1--6, 8--11, 21
|
| 4 |
Sep 21 |
3.1, 11.1, 11.2 |
Read sections 3.1, 11.1, and 11.2 up through definition 11.12.
3.1: Exercises
p.518: 2, 3, 5, 8, 10
p.528: 1--5
|
| 5 |
Sep 28 |
11.2 |
Read the rest of section 11.2, starting after definition 11.12.
p.528: 9--14, 17
|
| 6 |
Oct 5 |
11.3 |
Read section 11.3.
11.3: 1--7(odd), 8--11, 13, 15, 16, 18, 20, 21, 24, 30
|
| 7 |
Oct 12 |
11.4 |
Read section 11.4 up through and including p. 548.
11.4: 3,5,6,8,10,18,19,21
|
| 8 |
Oct 19 |
Planar Coloring, 13.1 |
Read section 13.1.
1. A graph is outerplanar if it can be drawn in the plane so that every vertex is on the outer face and no edge crosses another.
- (a) Let G be a graph and let H be the graph obtained from G by adding a new vertex adjacent to every other vertex. Prove that if G is outerplanar, then H is planar.
- (b) Find the maximum number of edges in an n-vertex outerplanar graph without loops or multiple edges.
13.1: 2,3,5. Translation of 5 to English: Prove or disprove. For each vertex u in an edge-weighted graph, some shortest path from u to another vertex traverses at least one edge of minimum weight.
|
| 9 |
Oct 26 |
13.2, 13.3 |
Read sections 13.2 and 13.3 up through and including Theorem 13.3 on p. 646-647.
13.2: 1,2,3,4,5(a)
13.3: 1
|
| 10 |
Nov 2 |
13.3, 13.4 |
Read sections 13.3 from Theorem 13.3 on p. 646-647 and section 13.4.
13.3: 3,6,7
13.4: 2,3,4,7 (Hint for #7: Corollary 13.6)
|
| 11 |
Nov 9 |
13.4, Stable Matchings |
Read section 13.4; review class notes on Stable Matchings and the Gale--Shapley Algorithm.
13.4: 2,3,4,7 (Hint for #7: Corollary 13.6)
Stable Matchings: Five men (1,2,3,4,5) and five women (a,b,c,d,e) have the following preference lists:
| 1: baced |
a: 13542 |
| 2: abecd |
b: 42351 |
| 3: bcade |
c: 41325 |
| 4: abdce |
d: 32154 |
| 5: adecb |
e: 14532 |
- Find the stable matching that results when the men propose.
- Find the stable matching that results when the women propose.
- Which couples, if any, are matched in every stable matching?
|
| 12 |
Nov 16 |
16.1, 16.5 |
Read sections 16.1 and 16.5.
16.1: 1(a-d,f),3,4,5
16.5: 1,2,3
|
| 13 |
Nov 30 |
16.6 |
Read section 16.6.
16.6, p. 772: 1-4,5(a,b,c)
|
| 14 |
Dec 7 |
16.7 |
Read section 16.7.
16.7, p. 772: 6a(i-iv), 7, 8
|