Wednesday March 26: Introductory Lecture, Overview of Section 1 of book. Assignment: Read Section 1 for Friday.
Friday March 28: Class Activity: Finish Section 1 and begin Section 2. Assignment: Read Section 2 for Monday.
Monday March 31: Class Activity: Continue Section 2. Assignment: Do problems 1.1.4, 1.1.5, 1.1.7 (I don’t think it deserves its minus), 1.1.10, 1.1.14 (the graph theoretic generalization is not very impressive), 1.1.22, 1.1.34, 1.2.2, 1.2.4, 1.2.6, 1.2.8, 1.2.10, 1.2.17, 1.2.20, 1.2.26, 1.2.38 for Wednesday April 2.
Wednesday, April 2: Class Activity: Finish Section 2. Assignment: Read Section 3 for Friday.
Friday, April 4: Class Activity: Begin Section 3. Assignment: Read Section 4 for Monday.
Monday, April 7: Class Activity: Complete Section 3. Assignment for Wednesday: Do problems 1.2.29, 1.2.40, 1.3.1, 1.3.2, 1.3.4, 1.3.5 (This is a really good problem, but it doesn’t deserve the minus sign for the cycle part! Hint: In how many ways can you extend a P3 to a C4? How many P3s are there in a C4?), 1.3.12 (Notice there is a hint in the back of the book; however generalizing is easier said than done!), 1.3.17, 1.3.20, 1.3.23, 1.3.31 (Note, assume that ni and n are nonnegative in part b.), 1.3.40.
Bonus problems (optional) 1.3.41, 1.3.50.
Wednesday, April 9: Class Activity: Cover Section 4. Assignment: Read Chapter 2 Section 1 for Friday.
Friday April 11: Class Activity: Cover Chapter 2 Section 1. Assignment: Read Chapter 2 Section 2 for Monday.
Monday April 14: Class Activity: Begin Chapter 2 Section 2. Assignment for Wednesday: Do Problems 1.4.3, 1.4.5, 1.4.9, 1.4.14, 1.4.19, 1.4.27, 2.1.1 (just do maximum degree k), 2.1.2, 2.1.6, 2.1.13, 2.1.20, 2.1.33, 2.2.1, 2.2.6, 2.2.8. Bonus problems (Optional). 1.4.35, 1.4.38, 2.1.58, 2.1.73
Wednesday April 16: Class Activity: Discuss Prufer Codes.
Schedule for first exam. The take-home portion of the first exam will be passed out on Wednesday April 16, and will be due at 5PM on Friday April 18. The in class portion of the exam will be at 9AM on Thursday April 17.
Friday April 18: Assignment: Read Chapter 2 Section 3 for Monday.
Monday April 21: Class Activity: Cover Spanning trees in Chapter 2 Section 3. Assignment for Wednesday. Turn in problems 2.2.1 and 2.2.8 if you didn’t already do so. Do Problem 2.2.12, 2.3.1, 2.3.2, 2.3.3, 2.3.5, 2.3.10, 2.3.13, 2.3.14.
Wednesday April 23: Class Activity: Cover spanning trees in Chapter 2 Section 2. Assignment for Friday. Read Section 3.1 through page 115.
Friday April 25: Assignment for Tuesday. Read Section 3.1 through page 115
No class Monday April 28. Class will be at 8:45AM Tuesday April 29 instead.
Tuesday April 29: Class Activity: Begin Section 3.1. Assignment for Wednesday April 30 Do problems 2.2.2, 2.2.3, 2.2.7, 2.2.17 (Hint: one way to do this is to use row operations to convert the determinant you need to compute into a simpler form.), 3.1.1, 3.1.2, 3.1.3, 3.1.8, 3.1.11, 3.1.19, 3.1.24, 3.1.28 Bonus 2.2.19, 2.3.19, 3.1.37
Wednesday April 30: Assignment for Friday May 2: Read Section 3.2 through Theorem 3.2.1
Friday May 2: Class Activity. Finish Section 3.1 and begin Section 3.2. Assignment for Monday May 5: Continue reading Section 3.2. Start studying for exam!
Monday May 5: Class activity: Finish section 3.2 if possible. Assignment for Wednesday May 7: Do Problems 3.1.4, 3.1.6, 3.1.10, 3.1.30, 3.2.1, 3.2.2, Bonus: Prove that Edmonds’ blossom algorithm described in Section 3.3, p142-145 works. It is fine to look up Edmonds’ paper about it for help.
Schedule for second exam. The take-home portion will be passed out on Wednesday May 7 and be due on Friday May 9 at 5PM. The in class portion will be at 9AM on Thursday May 8.
Wednesday May 7: Finish section 3.2. Assignment for Friday, May 9, turn in take home portion of exam!
Friday May 9: Start Section 5.1. Assignment for Monday May 12, Read Section 5.1.
Monday May 12: Finish Section 5.1. Assignment for Wednesday May 14. Do Problems 5.1.1, 5.1.4, 5.1.8, 5.1.9, 5.1.11, 5.1.15, 5.1.20, 5.1.31, 5.1.33, 5.1.51. Bonus: In the proof of the Hungarian algorithm, the weights are assumed to be rational numbers rather than real numbers. Further, in the discussion of the real number case, the book uses a special way to select the vertex cover Q; namely it uses the Q that the marking algorithm gives. Figure out what can go wrong with the real numbers. Does the algorithm given in the proof of the Hungarian algorithm just take a long time, or could it take forever, or could it simply stop without giving a maximum weight matching if we make the wrong choices of Q? Also 5.1.46.
Wednesday May 14: Finish Brooks Theorem. Assignment for Friday May 16. Read section 4.1, focusing on Blocks p155 and 156.
Friday May 16: Start Planarity. Assignment for Monday May 19: Read Section 6.1.
Monday May 19: Finish Section 6.1, Touch on Section 6.2. Due Wednesday May 21: Do Problems 4.1.6, 4.1.34 a, b. Also show that the block-cutpoint graph of a connected graph is connected. Hint: If there is a path between vertices in two blocks of G that share a cutpoint of G, does the path have to include the cutpoint? 5.1.3, 6.1.1, 6.1.2, 6.1.3, 6.1.8, 6.1.9, 6.1.10, 6.1.12, 6.1.21, 6.1.25. Bonus 4.2.16, 5.1.30
Wednesday May 21: Finish Section 6.3, restricted to graph coloring.
Friday May 23: Return to Section 5.3, the chromatic polynomial. For next Wednesday read Section 5.3, and do the following problems: 5.3.1, 5.3.3, 5.3.4, 5.3.11, 5.3.18, 6.2.1, 6.2.2ab 6.2.3 Hints: Count the number of vertices and edges. There is a straight line planar drawing of the graph you want somewhere in the book. I found it, and I bet you can., 6.2.4 (not as easy as the author thinks it is), 6.3.2, 6.3.3, 6.3.6 Hint start with at most 11 vertices. This problem is related to another one in this assignment. Bonus 5.3.12, 6.3.14
Monday May 26. No class; holiday/first day of reading period
Wednesday May 28: We will go over the homework due. Any additional time will be devoted to trying to answer any questions you bring with you! The take-home ortion of the final will be handed out. It will be due June 2 at noon in Prof. Bogart’s office.
Monday June 2: “In class” portion of final exam. Scheduled by registrar for 8:00 AM. Once I have it ready I will know if we can start a bit later than 8:00 and still have everyone done by 10:00. I will then either confirm the 8:00 AM time or modify it here on the schedule.