A fond farewell
Problem of the day
A matching in a graph is a set of disjoint edges (i.e. edges that do not share any vertices). Give a linear-time algorithm to find a maximum matching in a tree.
Six pirates must divide $300 among themselves.
The division is to proceed as follows.
The senior pirate proposes a way to divide the money. Then the pirates vote.
If the senior pirate gets at least half the votes he wins, and that division remains.
If he doesn't, he is killed and then the next senior-most pirate gets a chance
to do the division. Now you have to tell what will happen and why
(i.e. how many pirates get killed and how is the money divided).
All the pirates are intelligent and the first priority is to stay alive
and the next priority is to get as much money as possible
(and they want to elevate their rank only after that).
No class Tuesday (4th)
AND Test2 Thursday (6th)
Graph flavors (simple, directed, weighted, acyclic, sparse)
Adjacency Matrices vs Adjacency Lists
Traversal (BFS, DFS, and Riding the rails)
Edge classifications (Tree, Forward, Back, Cross)
BFS: Finding short paths, Root distance
BFS: Bipartite detection
BFS: Connected Components
DFS: Ancestry, Parentheses property
DFS: Find cycles
DFS: Find articulation vertices
DFS: Topological Sorting
Strongly Connected Components
Minimum Spanning Trees
Graph Cuts, "Safe" edges, Bridges
Prim, Kruskal, Boruvka
Weighted Short Paths
Maximum Flow / Minimum Cut
Principles for spotting graph problems
Don't forget (final is cumulative) you also have the powers of:
Counter-Examples and Correctness
Arrays vs Linked-Lists
Stacks vs Queues
Binary Search Trees
Selection and Insertion Sorts
Binary Search and friends
Techniques for applying these
So what next?
1) A taste of real world graph theory
2) Practice for the test
THEN (11th) We start the hard stuff!
Art Gallery Guarding (Open for results)
Stable Marriage Problem (Nobel prize)
Graph Isomorphism (Don't know if P or NP)
Ramsey Numbers (At a party of at least 6 people some 3 will know each other or not know each other).
Transfer Matrix Method (How many words of length k in letters a and b don't have consecutive b's?)
Random Walks on graphs!
Work any problems from chapter 5 or chapter 6 with weight \( \leq 5\)