Goodbye Graphs

A fond farewell

Andy Novocin

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.

Math Problem of day

Project Euler 18 / 67

Interview Question

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
Dijkstra, Floyd-Warshall
Transitive Closure
Maximum Flow / Minimum Cut
Principles for spotting graph problems

Don't forget (final is cumulative) you also have the powers of:

RAM model
big-Oh Analysis
Counter-Examples and Correctness
Arrays vs Linked-Lists
Stacks vs Queues
Binary Search Trees
Priority Queues
Hash Tables
Selection and Insertion Sorts
Merge Sort
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!

Bring... It... On!

Explore these

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!

Practice Problems

Work any problems from chapter 5 or chapter 6 with weight \( \leq 5\)