Design and Analysis of Algorithms  Homework 1

CS 535 Design and Analysis of Algorithms 
Homework 1 version 1.1

Remote students: use blackboard to submit your solutions. In-class students: hard coppies are
required. Blackboard is optional (and useful).
Problem 1 Suppose that you have a “black-box” worst-case linear-time median subroutine. Give
a simple, linear-time algorithm that, given an array A[1..n] and a positive integer i ≤ n finds the
i
th smallest element of A. Present pseudocode using procedures from the textbook or notes; give
complete specifications and state the running time of the procedure in terms of its parameters.
Problem 2 Problem 9-2 (Weighted Median) from the textbook. It has the same number in the
second edition of the textbook.
Problem 3 Consider the following recursive algorithm for computing minimum spanning trees.
Given as input a complete graph G = (V, E), randomly partition the set V of vertices into two
sets V1 and V2 such that |V2| = 1. Let E1 be the set of edges that are incident only on vertices in
V1. Recursively solve a minimum spanning tree problem on the subgraphs G1 = (V1, E1). Finally,
select the minimum-weight edge in e that crosses the cut (V1, V2), and use this edge to unite the
resulting two minimum spanning trees into a single spanning tree.
1. Give an example (a weighted graph!) showing that the algorithm can fail to produce a
minimum spanning tree (if the partition is done in worst-case manner). Explain what the
algorithms does and why the output is not optimum.
2. Argue that the algorithm will produce a minimum spanning tree, if (with a lot of luck) the
partition is always done in best-case manner.
Problem 4 Let G = (V, E, c) be a weigted undirected graph where all the costs ce, for e ∈ E, are
strictly positive and distinct. Let T be a minimum spanning tree in G = (V, E, c). Now suppose
we replace the cost of each edge e ∈ E by c
′
e = c
2
e
, creating the instance G′ = (V, E, c′
). Prove or
disprove: T is a minimum spanning tree in G′
.
Now assume s, t ∈ V are also given, and P is a shortest s − t path in G. Prove or disprove: P
is the shortest s − t path in G′
.
1