MA415 HOMEWORK #7
Due Monday, April 17

Here's what's going on the week of April 10-14:

1. Laura Spencer will conduct the class. She will go over material in Section 6.3 that I do not cover on Friday, April 7.
2. On Monday, April 10, she will collect any submissions to Homework #6 that weren't turned in on Friday, April 7. She will also hand out solutions to this assignment.
3. On Wednesday, April 12, she will administer the course evaluation during the last 10-15 minutes of class. Please respond thoughtfully, as I use these evaluations to reflect on my teaching. On the space for written comments, please answer the following questions:
   1. How was my teaching?
   2. What do you think of the book?
   3. What do you think of the time spent in class working on problems? Too much? Too little? As a result do you think we covered too little material?
   4. Do you have any other comments about the course?
4. The third exam will be on Friday, April 21. It will cover Sections 5.5, 6.1, and 6.2.

   You should know how to prove the following Theorems:

   1. Theorem 5.11
   2. Theorem 6.3
   3. Theorem 6.6
   4. Corollary 2 following Theorem 6.6
   5. Theorem 6.8

   You should know how to do the following for a given graph:

   1. Breadth-first search
   2. Dijkstra's algorithm
   3. Computing the number of spanning trees using Theorem 6.8
   4. Computing the number of spanning trees using the Matrix Tree Theorem
   5. Converting spanning trees of into Prüfer codes and vice versa, as in the proof of Theorem 6.9

   We did not discuss Depth-First Search, so we won't include it on this exam.

   Of course, you should know all the definitions, the statements of all the theorems, etc.

   The exam may be slightly different from the previous ones. I will definitely ask you to prove at least one theorem. I may choose some of the non-advanced problems from the book, but I may also/instead include some questions of my own, some of which may be short answer questions.

5. The homework assignment due on Monday, April 17, is Section 6.3, #1, 3, 7, 8, 16, 18.

• About this document ...