



Homework 3
Disjoint Sets, Sorting and Graphs
Due: Wednesday, March 8, beginning of class
This assignment is designed to give you practice with
unionfind, sorting techniques and graph algorithms discussed in the class, along
with some simple applications.
Note: Please review the collaboration policy on the course web
page. You must mention the names of fellow students who you worked with
on this assignment.
Total: 90 points. 10 points for each problem.
 [Unionfind] Suppose
you start with elements a through j with each in its own
set, and perform the following operations (Showing your intermediate steps
may allow partial credit):
find(d), union(d,a), union(b, c), union(h,j), find(c), union(h,b),
find(j), union(b,a).
 Without unionbysize
or path compression, and choosing the root of a union by selecting the
alphabetically smaller node, show the final uptree
forest that results from the above operations. At what depth does node j
end up in the final forest?
 Repeat part a. but
this time with unionbysize. Break any ties by giving preference to the
alphabetically smaller node.
 Repeat part b. but now
add path compression as well.
 [Sorting] Problem 7.17,
page 262. For part (c) give an
averagecase analysis. (runtimes for mergesort)
 [Sorting] Problem 7.20,
page 262. For part (c) give an
averagecase analysis. (runtimes for quicksort)
 [Sorting] Sort an
array containing: 3,1,4,8,5,9,2,6,7,0, using quicksort
with medianofthree partitioning.
Use the code in the book for
this and a cutoff value of 3 (pages 246 and 247). Show what the recursive calls are
and what the pivot and array are at the beginning of each step. Be clear about when the cutoff
kicks in and insertion sort is used.
 [Sorting] (5 points each part)
 Problem 7.3,
page 261 (inversions)
 Problem 7.41, page
264 (comparison sorting 4 elements)
 [Graphs] Suppose you
are given a graph that has negativecost edges but no negativecost
cycles. Why does the following strategy fail to find shortest paths:
uniformly add a constant k to the cost of every edge so that all
costs become nonnegative, run Dijkstra's algorithm, return the result
with edge costs reverted back to the original costs (i.e. with k
subtracted). Give an argument as well as a small example where it fails.
 [Graphs] Problem 9.1,
page 341 (topological sort)
 [Graphs] Problem 9.
5, parts (a) and (b) page 342. Be sure to give the path AND its length.
(weighted and unweighted shortest path)
 [Graphs] Problem 9.
15, parts (a) and (b) page 343. Start Prim’s algorithm with node
D. (MST)
