(a) (4%) Explain why a spanning tree contains exactly n- 1 edges. 3. (b) (4%) Derive the best case and the worst case time complexity of quick sort. (c) (4%) Quick sort is not stable. Give an example of an input list in which the order of records with equal keys is not preserved. (d) (4%) What kind of heaps is required in heap sort with non-decreasing order? Why? (e) (4%) Consider the single source all destinations problem. Explain why it is required that the graph have no cycles of negative length when negative edge lengths are permitted. (f) (6%) Consider the set representation using trees. If the sets being represented are pairwise disjoint, explain what the collapsing rule is. What scenario is more beneficial for the find operation applying collapsing rule? Why