Homework 2 Optional Problems

Consider a connected undirected graph 𝐺 with edge costs, which need not be distinct. Prove the following statement or provide a counterexample: for every MST 𝑇 of 𝐺, there exists a way to sort 𝐺’s edges in nondecreasing order of cost so that Kruskal’s algorithm outputs the tree 𝑇.

ANSWER: Given a MST 𝑇, to obtain this tree with Kruskal’s algorithm, we order the edges first by their weight, and resolve ties by picking an edge first if it is contained in 𝑇. With this ordering, we will find 𝑇.

Consider a connected undirected graph 𝐺 with distinct edge costs that are positive integers between 1 and 𝑛3, where 𝑛 is the number of vertices of 𝐺. How fast can you compute the MST of 𝐺?

ANSWER: We may use Radix Sort instead of a comparison sort to sort in linear time. We don’t use Counting Sort ¹ because it’s going to take 𝑂⁡(𝑛3) time to go over the buckets. In general, Counting sort takes 𝑂⁢(𝑘 +𝑛) time, where 𝑛 is the size of the input and 𝑘 is the maximum value of the keys. Once sorted, we may use Kruskal’s algorithm to compute the MST in linear time.

Read about matroids. Prove that the greedy algorithm correctly computes a maximum-weight basis. For the matroid of spanning trees of a graph, this algorithm becomes Kruskal’s algorithm. Can you formulate an analog of Prim’s MST algorithm for matroids?

ANSWER: CLRS section 16.4 has an excellent introduction to Matroids. Also see the Metroid section in the curated list. Quoting CLRS:

A graphic matroid 𝑀𝐺 =(𝑆𝐺,𝐼𝐺) defined in terms of a given undirected graph 𝐺 =(𝑉,𝐸) as follows:

• The set 𝑆𝐺 is defined to be 𝐸, the set of edges of 𝐺.
• If 𝐴 is a subset of 𝐸, then 𝐴 ∈𝐼𝐺 iff 𝐴 is acyclic. That is, a set of edges 𝐴 is independent if and only if the subgraph 𝐺𝐴 =(𝑉,𝐴) forms a forest.

If we define the weight function such that weight 𝑤𝑒 of an edge 𝑒 is given by 𝑤𝑒𝑚⁢𝑎⁢𝑥∀𝑒 −𝑤𝑒, then Kruskal’s algorithm becomes a special case of the algorithm 𝐺⁡𝑅⁢𝐸⁢𝐸⁢𝐷⁢𝑌⁡(𝑀,𝑤) in CLRS.

Prim’s algorithm, on the other hand, maintains an induced subgraph 𝐹 =(𝑉′ ⊆𝑉,𝐸′ ⊆𝐸 ∣𝑒⁡(𝑣,𝑤) ∈𝐸′ ⟺ 𝑣,𝑤 ∈𝑉′). For connected graphs, 𝐹 is a tree, but (𝐸,𝐹) is not a Matroid since it doesn’t satisfy the hereditary property; removing an edge from a tree may render it disconnected. Therefore, it can’t be formulated in terms of greedy algorithm for Matroids.

Prove that our analysis of union-find with lazy unions and union by rank (but without path compression) is asymptotically optimal (i.e., there are sequences of operations where you do Θ⁡(log⁡𝑛) work on most of the operations).

ANSWER: The upper bound is proven is lecture video 7.3. For the lower bound, consider doing a find operation on the leaf node in a path of length log⁡𝑛 (the longest possible). Since we must traverse all nodes on the way to the root, the time taken is equal to the length of the path. Thus, time complexity of find is Θ⁡(log⁡𝑛).

Prove that in our union-find data structure with lazy unions, union by rank, and path compression, some operations might require Θ⁡(log⁡𝑛) time.

ANSWER: See Tarjan’s paper in the curated list.

ReferencesPermalink