Problem M: Beginning with the result from 238, use a partial fraction decomposition, together with our power series formulas, to find an explicit formula for $a_i$.
Week 13
Reading for Monday: Section 5.1
Group work for Monday: 207-208, 211-213
Reading for Wednesday: Start Section 5.2
Group work for Wednesday: 222-228
Homework due Tuesday 4/20:
Problem 213
Problem K: Suppose you can take between 0 and 3 apples, between 2 and 5 pears, and between 4 and 7 bananas. Suppose you want to take 10 fruits in total. How many ways are there to do this? Set up the problem using generating polynomials, you may use a computer to do the algebra.
Problem 226
Problem L: Recall the power series for $(1-x)^{-1}$ is $\sum x^k$.
(a) Since $(1-x)^{-2}$ is $(1-x)^{-1}(1-x)^{-1}$, find its power series by evaluating $(\sum x^k)(\sum x^k)$.
(b) Since $(1-x)^{-2}$ is the derivative of $(1-x)^{-1}$, find its power series by evaluating the derivative of $\sum x^k$.
Week 12
Reading for Monday: Start The Coloring of Graphs (via blackboard)
Reading for Wednesday: Finish The Coloring of Graphs
Group work for Wednesday: CoG exercise 10
Homework due Tuesday 4/6:
Problem G: What is the chromatic polynomial of the complete graph on $k$ vertices? Explain your answer.
Problem H: Use the reduction algorithm to calculate the chromatic polynomial of the pentagon graph (the edges are (1,2),(2,3),(3,4),(4,5),(5,1)).
Problem I: The degree of the chromatic polynomial is equal to the number of vertices of the graph. Use induction and the deletion/contraction recurrence to prove this is always the case.
Problem J: The constant term of the chromatic polynomial is always equal to $0$. Explain why this is always the case. [Hint: how many ways are there to color a graph using a palette of $0$ colors? What does this say about $p(0)$?]
Reading for Wednesday: Finish section 4.5.1, Read 4.6
Group work for Wednesday: 196-198, 200-202
Homework due Thursday 4/1:
Problem 194: Describe Kruskal’s (or Prim’s) algorithm carefully, and briefly explain why it “works”
Problem 198
Problem E: Draw a connected weighted graph (not a tree) with at least 7 vertices and at least 14 edges. Run Kruskal’s algorithm for the graph to find the minimum spanning tree.
Problem F: For the same graph as in Problem E, choose a special vertex $v$ and run Dijkstra’s algorithm to find the tree of shortest paths from $v$. Compare with the tree from part $E$.
Week 10
Reading for Monday: Start section 4.3
Group work for Monday: 164-170
Reading for Tuesday: Finish section 4.3
Group work for Wednesday: 172-178
Homework due Tuesday 3/23:
Problem A: Explain why the last element $b_{n-1}$ of a Prufer code sequence B is always $n$.
Problem B: Find the tree for the following prufer code: 1,2,1,3,1,4,1,5,1,6
Problem C: Write all sixteen possible Prufer codes with $n=4$ (so the codes have length 2) and draw the corresponding trees.
Problem D: What is the relationship between the degree of a vertex, and the number of times the vertex occurs in the Prufer code? Give a complete explanation (proof) your answer is correct.
Week 9
Monday: Catch-up and homework questions
Tuesday: Exam posted, homework 8 due
Wednesday: No class
Sunday 3/14: Exam due, pi day
Week 8
Reading for Monday: Section 4.1
Group work for Monday: 141-146, 149-150
Reading for Wednesday: 4.2
Group work for Wednesday: 151-156, 158-159
Homework due Tuesday 3/9: 141, 146, 152, 155
Week 7
Reading for Monday: Section 3.3 again
Group work for Monday: 105-110, 114, 116
Reading for Wednesday: Section 3.3.1, 3.3.2
Group work for Wednesday: 118, 120, 122-123, 126
Homework due Tuesday 3/2: 107, 112, 123, 126
Week 6
Holiday on Monday!
Reading for Wednesday: Preview section 3.3
Group work for Wednesday: Review, catch up, bonus problems!