All members of the collaboration group are expected to participate fully in solving collaborative problems, and
peers will assess performance at the end of the assignment. Note, however, that each student is required to
write up their solutions individually. Common solution descriptions from a collaboration group will not be accepted.
Furthermore, to receive credit for a collaboration problem, each student in the collaboration group must actively and
substantially contribute to the collaboration. This implies that no single student should post a complete solution to
any problem at the beginning of the collaboration process.
Problems for Grading
- [20 points] Write a Θ(m + n) algorithm that prints the in-degree and the out-degree of every vertex in an
m-edge, n-vertex directed graph where the directed graph is represented using adjacency lists. (Hint: See
Figure 2.2 on page 590 of CLRS for a diagram and description of adjacency list representations of graphs.) - [10 points] CLRS 9.3-9: Professor Olay is consulting for an oil company, which is planning a large pipeline
running each to west through an oil field of n wells. The company whats to connect a spur pipeline from each
well directly to the main pipeline along a shortest route (either north or south), as shown in Figure 9.2 in the
textbook. Given the x- and y-coordinates of the wells, how should the professor pick the optimal location of the
main pipeline, which would be the one that minimizes the total length of the spurs? Show how to determine
the optimal location in linear time, and prove the correctness and linear bound of the algorithm. - [40 points] Collaborative Problem–CLRS 5-1: With a b-bit counter, we can ordinarily only count up to 2
b − 1.
With R. Morris’s probabilistic counting, we can count up to a much larger value at the expense of some loss of
precision.
We let a counter value i represent a count of ni
for i = 0, 1, …, 2
b−1, where the ni
form an increasing sequence
of nonnegative values. We assume that the initial value of the counter is 0, representing a count of n0 = 0.
The Increment options works on a counter containing the value i in a probabilistic manner. If i = 2b − 1, then
the operator reports an overflow error. Otherwise, the Increment operator increases the counter by 1 with
probabilities 1/(ni+1 − ni), and it remains unchanged with probability 1 − 1/(ni+1 − ni).
If we select ni = i for all i ≥ 0, then the counter is an ordinary one. More interesting situations arise if we
select, say, ni = 2i−1
for i > 0 or ni = Fi (the ith Fibonacci number–See Section 3.2 in the text).
For this problem, assume that n2
b−1
is large enough that the probability of an overflow error is negligible.
(a) [20 points] Prove that the expected value represented by the counter after n Increment operations have
been performed is exactly n.
(b) [20 points] The analysis of the variance of the count represented by the counter depends on the sequence
of the ni
. Let us consider a simple case: ni = 100i for all i ≥ 0. Determine the variance in the value
represented by the register after n Increment operations have been performed. - [30 points] Collaborative Problem– In this problem we consider two stacks A and B manipulated using the
following operations (n denotes the size of A and m the size of B):
• P ushA(x): Push element x on stack A.
• P ushB(x): Push element x on stack B.
• MultiP opA(k): Pop min(k, n) elements from A.
• MultiP opB(k): Pop min(k, m) elements from B.
• T ransfer(k): Repeatedly pop an element from A and push it on B, until either k elements have been
moved or A is empty.
1
Assume that A and B are implemented using doubly-linked lists such the P ushA and P ushB, as well as a
single pop from A or B, can be performed in O(1) time worst-case.
(a) [5 points] What is the worst-case running time of the operations MultiP opA, MultiP opB, and T ransfer?
(b) [25 points] Define a potential function Φ(n, m) and use it to prove that the operations have amortized
running time O(1).