Homework 4, CS420, Spring 2020
Submit as a PDF scan. Make sure your name and I.D. number appear at
the top of it. Arrange your solutions so that they appear in order in the
PDF file. Check what you have submitted to make sure it is all legible
and nothing is missing.
1. Suppose Johnson’s algorithm doesn’t change the weight of any edge by more than
plus or minus r. Give a tight exact bound on how much it can change the total
weight of a cycle that has k vertices in it. I am looking for an exact bound, not an
asymptotic (big-Θ) bound. Explain your answer by showing algebraically how much
the reweighting label w of a vertex on the cycle can contributed to the reweighted
weight of the cycle.
2. Suppose you add a constant to all the reweighting labels at the vertices. What does
this do to the reweighted values. Justify your answer with algebra.
3. Suppose Johnson’s algorithm operates on a class of graphs that have no negative
cycle but that do have a zero-weight directed cycle that contains all the vertices. The
application in which these graphs arise make it obvious which are the edges of the
cycle; assume the edges of this cycle are given.
Give an algorithm to perform the reweighting that is faster than Bellman-Ford. Express
your bound as a function of n and/or m. Do not count the cost of performing
the n calls to Dijkstra’s algorithm once you have reweighted it.
You can express the steps of your algorithm in English, but you must do it in a way
that leaves no question about what the step does. Explain why it works.
To be safe, you may want to supplement your English description with pseudocode
to resolve any ambiguity that you could lose points for.
4. There is a long, straight beach several miles long with n houses along it. You want to
open up a bar-and-grill on the beach. Give an O(n) algorithm for finding a location
that minimizes the sum of distances to the n houses. The distances of all the houses
from the first house in the sequence are known precisely.
5. When we got an O(n) algorithm for selection, we divided the elements into groups of
five.
(a) What bound do we get if we use the same strategy on groups of seven instead of
groups of five?
(b) What about groups of three?
6. Suppose an array contains a set of ordered pairs (k, w), where k is the key of the pair
and w, a positive number, is the weight. The weighted rank of a key k is the total sum
of weights of pairs whose key is less than or equal to k.
Problem: Given a weight W between 0 and the sum of weights of all pairs in the
array, find the smallest key k whose weighted rank is greater than or equal to W.
(a) Give an O(n log n) algorithm for solving the problem.
(b) Describe an O(n) algorithm that uses our ability to find the median key in O(n)
time. Describe the steps of the algorithm. Be precise in your description of the
steps, which can include recursive calls and must address the base case.
(c) Give a recurrence for your algorithm and derive the O(n) bound for it.
(d) Write pseudocode for the algorithm, similar to pseudocode you have seen in our
readings. You may make calls to algorithms that are already defined in the text.