Write a program to convert from an adjacency list graph representation to an adjacency matrix. Say you have the following type definitions and you want to write the AdjMatrixGraph constructor.
struct AdjListElt {
int neighbor;
AdjListElt *next;
};
class AdjListGraph {
private:
int num_nodes;
// head[i] points to the first element in the ith vertex's adjacency list
AdjListElt **head;
friend class AdjMatrixGraph;
};
class AdjMatrixGraph {
public:
AdjMatrixGraph(AdjListGraph *source);
private:
int num_nodes;
int **matrix;
};
Consider the maximum number of triangles in a graph with n nodes and m edges, not necessarily planar. (A triangle has 3 distinct nodes connected by 3 distinct edges.) One simple bound you can give for this quantity is n choose 3 (n(n-1)(n-2)/6), since each triangle has three nodes as vertices. Give a stronger bound.
A popular conjecture is that every pair of people in the world is connected by ``six degrees of separation''. That is, no matter who you are if we tried hard enough we could find five people so that I know the first person, the first person knows the second, the second knows the third, the third knows the fourth, the fourth knows the fifth, and the fifth knows you. Say we test this conjecture by asking 10,000 people to list 40 people they know. How can we find the ``most separated'' pair?
Challenge problem: Say you're given a class schedule. Each of the classes you want to take has two sections at different time blocks. No time blocks overlap. You want to select a section from each class so that none of the selected sections overlap. How can you model this as a problem we've seen in class? (Question from Avrim Blum)
Challenge problem: In class we saw that every planar graph has at most 6n edges. This bound is appallingly weak: in fact every planar graph with at least 3 nodes has at most 3n-6 edges. Prove this. (You can still assume that any planar graph can be drawn with straight lines.)
Draw the breadth-first search tree and the depth-first search tree for the following graph. The neighbors are each node are listed in alpabetical order, so the nodes are inserted to the active list in that order.
K A F---H /| | | / C---B G---J \ | | \ | -----D---E---I
You are a Cretan (not cretin) princess who has decided to help Theseus defeat the Minotaur and escape from the labryinth. You've already equipped him with a phaser gun (set to stun - I only write G-rated problems) and a GPS system so that he can identify when he's at different intersections in the labyrinth. Theseus isn't too clever, though, so you also need to tell him how to efficiently visit every intersection and passage in the labryinth so he can find the Minotaur. What algorithm do you suggest? If each passage is a meter long, how far will Theseus have to walk? Your answre should be in terms of n, the number of intersections, and m, the number of passages; do not use big-O notation for your bound. Note that Theseus will have to travel down every passage at least once to be sure he has visited all passages. (Question from CLR; Michael Bender inspired the mythology adaptation.)
Challenge problem: A bipartite graph is a graph whose nodes can be partitioned into two sets so that every edge has an endpoint in each set. Give an efficient algorithm for determining whether a given graph is bipartite. (CLR question)
If it starts at the asterisked node, what will the shortest-path tree look like after Dijkstra's algorithm adds the first five edges in the following graph? What is the final shortest-path tree?
10 18 12 1
o-----o-----*-----o-----o
| | | | _/
12| 2| 1| 2| _/13
| 16 | 16 | 14 |/
o-----o-----o-----o
| | | |
1| 16| 5| 20|
| | | |
o-----o-----o-----o
15 2 22
In our analysis of Dijkstra's priority-first search algorithm we used a heap implementation of a priority queue. How long would a search take if we used an unordered list implementation instead? (Do version 2 of the algorithm, where the ants have calculators and we occassionally decrease priorities. We'll want an array indexing where the vertices are in the list so that we can decrease a priority in constant time.) What if we used a list ordered by priority?
What will the spanning tree look like after Prim's algorithm adds the first four edges in the following graph, if it begins at the asterisked node? What is the final minimum spanning tree for the graph?
10 18 12 1
o-----o-----*-----o-----o
| | | | _/
12| 2| 1| 2| _/13
| 16 | 16 | 14 |/
o-----o-----o-----o
| | | |
1| 16| 5| 20|
| | | |
o-----o-----o-----o
15 2 22
Prim's algorithm for minimum spanning trees only applies when the edges are undirected. Where does the proof fall through when the edges are directed?
An alternative minimum spanning tree algorithm is Kruskal's algorithm. In Kruskal's algorithm we take the lightest edge in the graph and place it into the spanning tree if it connects two vertices that haven't been connected yet. Then we take the second lightest edge and place it into the spanning tree if it connects two vertices that haven't been connected yet. We continue until all vertices are connected. Assume that we know how to check if two vertices are connected in O(1) time. How can we implement Kruskal's algorithm efficiently, and how much time will it take?
A consequence of the repeated-squaring algorithm is that, when k is a power of two, we can compute the kth power of a matrix using only O(log k) matrix multiplications. (Start with A, compute A'=A*A to get A^2, then compute A"=A'*A' to get A^4, then A"'=A"*A" to get A^8, and so on until we get up to A^k.) For arbitrary k, how can we find the kth power of a matrix using only O(log k) matrix multiplications?
In class we applied the minimum matching problem to matching freshmen to dorms. How long does this algorithm take?
When we initially wrote Floyd's algorithm we thought of the algorithm as using n+1 different matrices and included subscripts to distinguish them. Then I waved my hands and removed the subscripts. Why can we get away without the subscripts? Challenge problem: Suppose you were wrong on your last answer. What's another reason we can get away without subscripts? (CLR problem)