Office: Mathematics 715

Office Phone: 621-2463

Office Hours: TBA

Email: glickenstein@math.arizona.edu

- Thursday, December 11, 2-4 PM in Math 715.

- Friday, December 12, 10-12 AM in Math 715

- Exam 1 will be in class on October 8
- It will cover material through tournaments. REMEMBER THAT
30-50% OF THE EXAM COMES EXACTLY OUT OF HOMEWORK PROBLEMS, PROBABLY
ONES WHICH WERE NEVER REQUIRED TO BE TURNED IN.

- Exam 2 will be in class on December 3. It will cover everything
from pipeline problems trhough stable marriage.

- Final Exam will be Friday, Dec 12, 2-4pm. It will be
comprehensive.YOU MAY USE YOUR NOTES FOR THE EXAM.

- First batch: Introduction to graphs

- Second batch: Koenigsberg bridge problem and
Eulerian graphs

- Third batch: Shortest paths and Dijkstra's
algorithm

- Fourth batch: Connector problem
- Fifth batch: Planar graph and coloring problems
- Sixth batch: Digraphs, traffic, and tournaments.
- Seventh batch: Pipeline problems, networks, and flows.
- Eighth batch: Graphs as matrices and PageRank.
- Ninth batch: Matching, dancing, and stable marriage.
- Tenth batch: Small world phenomenon.
- Eleventh batch: Graph minor theorem and Kuratowski's theorem
- Twelfth batch: Graph Laplacians

- C. Introductory Graph Theory, by Gary Chartrand, published by
Dover.

- BM. Graph Theory and Applications, by J.A. Bondy and U.S.R. Murty, available here.
- T. Extra material on the Four Color Theorem: Paper by Robin Thomas
- BL. The $25,000,000,000 Eigenvector: The Linear Algebra Behind Google by K. Bryan and T. Leise.
- M. Notes
on Stable Marriage Problem, by Albert R. Meyer from MIT. You can
ignore the first part on state machines.

- EK. Notes on Small World Phenomena, by David Easley and Jon Kleinberg from Cornell.
- K. The
Small World Phenomenon: An Algorithmic Perspective, by Jon
Kleinberg.

- WS. Collective dynamics of `small-world' networks, by Duncan Watts and Steven Strogatz, published in Nature (you need UA access to get this paper).
- H. Lecture
notes on Graph Minors, by Jan van den Heuvel.

- D. Graph theory, by Reinhard Diestel. Electronic edition
available here.
We will use some material from Chapter 12.

- C-1, problems 21, 22
- C-2, problems 2, 3, 5, 6, 7, 10, 14,15, 16, 18, 24, 25
- Induction Problem: Use mathematical induction to prove that the sum of an even number of odd numbers is even and an odd number of odd numbers is odd. (Hint: recall that even numbers can be enumerated as 2n for n=0,1,... and that odd numbers can be enumerated as 2m+1 for m=0,1,2,...)
- C-2, problems 36,40,43,45,46,53,57.
- C-3, problems 1, 2, 7, 17, 18, 23, 24
- BM, problems 1.8.1, 1.8.2, 1.8.3
- C-4, problems 1,2,6,7,9,12,14
- C-9, problems, 1, 2, 3, 6, 8, 11, 12, 19, 20, 21, 23, 25, 26.
- C-10, problems 11, 12, 13, 14, 15, 16
- C-7, problems 3, 7, 8, 11, 13, 17, 19
- Extra problem: Check directly that every tournament of order 4 has a hamiltonian path.
- BM-11, 11.3.2, 11.3.4
- BL-Exercises 1, 3, 5, 9, 10, 11, 12, 14
- C-5, problems 5, 6, 10, 12, 14, 20, 24, 27
- Stable Marriage problems.
- Problems on small world, graph
minors, and Laplacians.

- Due Wednesday, Sept 10: C-2 problems 2, 16, Induction Problem listed above.
- Due Wednesday, Sept 17, C-2 problem 36, C-3 problems 18, 24.
- Due Wednesday, October 1, BM-1.8 problem 1.8.1, C-4 problem 14, C-10 problem 12.
- Due Wednesday, October 22, C-7 problem 19, BM-11.3 problem 11.3.2.
- Due Friday, November 7, BL exercises 1,5,10
- Optional homework, due Wednesday, December 10, from problems on small world, graph minors, and Laplacians, problems 2,3,7

- Backward Static Program Slicing, Kevin Coogan
- Tutte Embedding Theorem: How to Draw a Graph, Kyri Pavlou
- Stable Marriage Problem, William Kozma
- On Channel-Discontinuity-Constraint Routing in Multi-Channel Wireless Infrastructure Networks, Abhishek Gopalan and Swaminathan Sankararaman
- ROMaN: Revenue driven Overlay Multicast Networking, Varun Khare