This is from some other textbook -- I forget which one.
In a connected graph, a bridge edge is defined to be any edge whose removal would make the graph no longer connected. An articulation point is defined to be any vertex whose removal (along with its incident edges) would make the graph no longer connected.
Write and analyze an efficient algorithm which takes in an undirected, connected graph and finds all its bridge edges (3 points).
Write and analyze an efficient algorithm which takes in an undirected, connected graph and finds all its articulation points (3 points).
For either of these, you'll get partial credit for a correct but inefficient algorithm. Hint: Start by drawing a graph with a single bridge edge or a single articulation point, run a breadth-first or depth-first search on it, and see what's special about the bridge edge or articulation point. Then try one with two bridge edges or two articulation points....
This is problem 3-9 from Kleinberg & Tardos.
Suppose an n-node undirected graph has two vertices s and t that are more than n/2 steps apart (i.e. the shortest distance from s to t is strictly more than half the number of vertices in the graph). Prove that there is some third vertex v in between so that if you remove v, it is no longer possible to get from s to t. Give an algorithm with running time O(n+m) to find such a vertex v.
This is based on problem 4-29 from Kleinberg & Tardos.
Recall that the degree of a vertex in a graph is how many edges are connected to it, i.e. how many next-door neighbors it has. Obviously, any n-vertex graph determines a list of n natural numbers, the degrees of the various vertices in the graph. For example, the graph with adjacency matrix
| a | b | c | d | |
|---|---|---|---|---|
| a | 0 | 1 | 0 | 0 |
| b | 1 | 0 | 1 | 1 |
| c | 0 | 1 | 0 | 1 |
| d | 0 | 1 | 1 | 0 |
With that as background, let's look at the opposite problem. Write and analyze a polynomial-time algorithm which, given a list of natural numbers d1, d2, ... dn, tells whether or not there is a graph with exactly those degrees. You're not allowed to have multiple edges between the same two vertices, nor edges from a vertex to itself.
This is problem 5-1 from Kleinberg & Tardos.
Imagine you are given two n-element sorted arrays, and you want to find the median element of the combined list. Each array gives you constant-time access to (say) the k-th-smallest element, but this constant is fairly large, so you want to do as few array accesses as possible. Of course, you could merge the two arrays into a single sorted array in O(n) time, then grab the middle element in O(1) time, but let's try to do better. Write and analyze an algorithm to find the median element of the combined 2n-element list in only O(log(n)) array accesses.
Exercise 9.1.4.1 "prefix sums". Assuming you have as many processors as you want, what's the fastest you can generate all N prefix sums? How much speed-up is this? Can you do it without increasing the cost (i.e. time-processor product) over the obvious single-processor algorithm?
Exercises 10.6.7.1 and 10.6.7.2 in the McConnell textbook.
Programming: based on the exercise at the end of chapter 8 of the McConnell textbook. You may do this in any programming language that both you and I know and that runs at Adelphi.
Note: even if you don't get all three of parts 2, 3, and 4 working, I still want you to run the timing tests of part 5 on whatever you have got working.
Write a function which, given n and k, generates a complete (i.e. every two vertices have an edge between them) undirected graph of n vertices, with edge weights chosen randomly from 0 to 100.
Write a function which, given the graph from part 1 and a vertex in the graph, finds a minimum spanning tree using the Dijkstra-Prim algorithm, starting from that vertex. Test it and make sure it produces correct answers.
Write a function which, given the graph from part 1, finds a minimum spanning tree using the Kruskal algorithm, using just a "which tree is this vertex in?" table to keep track of the unions and finds and avoid cycles. Test it and make sure it produces correct answers.
Write another Kruskal-algorithm function, but using the inverted-tree representation to keep track of unions and finds. Test it and make sure it produces correct answers.
Run each of these three functions a number of times on graphs of various sizes, and measure how long it takes each one to run. What conclusions can you draw about the efficiency of Dijkstra-Prim, Kruskal-with-table, and Kruskal-with-inverted-trees?