CSC 226: Problem Set 1
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSC 226: Problem Set 1
Problem Set 1
MSTs
2022
1 Proof of Cut Property Theorem (10 marks)
Assume all edge weights are distinct. Recall the Cut Property Theorem:
If (S,V / S) is a cut for graph G = (V,E), then the minimum-weight edge crossing the cut is contained in the minimum spanning tree.
Consider this modified version of part of the proof of the Cut Property Theorem:
Let e be a minimum-weight crossing edge for the cut (S,V / S). Let T be a spanning tree not containing e. Since T is a spanning tree, there must exist an edge in T that crosses the cut (S,V / S); select an arbitrary such edge and call it e\ . Form a new tree T\ by starting with T, adding edge e, and removing edge e\ .
(a) Assuming the new tree T\ is a spanning tree, show that T cannot be a minimum spanning tree.
(b) Is T\ guaranteed to be a spanning tree? If so, prove that it is. If not, give a counterexample.
A small guide on the work to be done for part (b): If you prove T\ is a spanning tree, then your proof must hold for an arbitrary connected, weighted graph G with an arbitrary choice of the cut (S,V / S). On the other hand, if you produce a counterexample, you need to produce a graph G, specify a cut (S,V / S) along with a minimum-weight crossing edge e, and specify an edge e\ .
2 The effect of modifying the weights (10 marks)
Let G be an arbitrary connected, weighted graph with unique edge weights. Suppose that the MST is T. Now, consider the graph G\ formed by starting with G and multiplying each edge weight by 2.
(a) If all the edge weights in G are nonnegative, is the MST T\ of G\ the same as the MST T for G? If you say yes, prove it (and if it is helpful for you, your proof can make use of any MST algorithm from class that we proved to be correct, i.e., Prim’s algorithm or Kruskal’s algorithm). If you say no, prove that T and T\ can be different by producing a simple counterexample (i.e., try to avoid a complicated one that uses lots of vertices and edges).
(b) Suppose that the edge weights are not necessarily nonnegative. Does the answer to part (a) change? Explain why or why not. Support your answer via a proof, just like in part (a). If you are able to, you may heavily reuse parts of your proof.
CSC 226: Problem Set 1
3 Kruskal’s algorithm runtime in a special case (5 marks)
Suppose we use an implementation of Kruskal’s algorithm that uses a priority queue (implemented as a binary heap) over edges and Weighted Quick-Union with Path Compression. In this question, we explore the runtime analysis of this implementation when given a connected, weighted graph G = (V,E) represented as an adjacency list. For simplicity, assume each call to Union costs log* V and each call to Connected also costs log* V .
Assume that the first V − 1 edges considered by the algorithm will be added to the MST. Also, assume that E = O(V). Under these assumptions, use big-O notation to give an asymptotic upper bound on the runtime of this implementation of Kruskal’s algorithm. Your final answer should be as simple as possible (if you have a sum of multiple terms, drop any term that asymptotically is smaller than another term), and it should grow as slowly as possible as well. Be sure to show your work.
4 Inverted human pyramid scheme (10 marks)
In this problem, we consider constructing an inverted human pyramid composed of n acrobats, all of the same height and infinitely strong.1 At the start, each acrobat stands separately in a singleton inverted human pyramid. Then the director (who is not one of the acrobats) orders two acrobats to join their respective inverted human pyramids. The join is performed as follows. Consider the acrobat at the base of each of the two pyramids. If one pyramid is shorter than the other, select the acrobat at the base of the shorter pyramid. If the pyramids are of equal height, select one acrobat
arbitrarily. Now, the selected acrobat will stand directly on top of the acrobat at the bottom of the other pyramid. Both before and after this join process, the person at the bottom of the shorter pyramid will still have the same configuration of people above them. For clarity, see the two examples below.
(b) Example 2, n = 6
Figure 1: Two examples. The colors are used only to help you understand the join process.
We say the height of an inverted human pyramid is its number of layers. So, a singleton pyramid has a height of 1. In Example 2, “After”, the leftmost inverted pyramid has a height of 1 and the rightmost inverted pyramid has a height of 3.
Prove by induction that, after any number of joins, the height of any inverted human pyramid is at most log2 (n) + 1.
2022-09-27