All members of the collaboration group are expected to participate fully in solving collaborative problems, andpeers will assess performance at the end of the assignment.…

All members of the collaboration group are expected to participate fully in solving collaborative problems, andpeers will assess performance at the end of the assignment Note, however, that each student is required towrite up their solutions individually Common solution descriptions from a collaboration group will not be acceptedFurthermore, to receive credit for a collaboration problem, each student in the collaboration group must actively andsubstantially contribute to the collaboration This implies that no single student should post a complete solution toany problem at the beginning of the collaboration processProblems for Grading

20 points Write a Θ(m + n) algorithm that prints the in-degree and the out-degree of every vertex in anm-edge, n-vertex directed graph where the directed graph is represented using adjacency lists (Hint: SeeFigure 22 on page 590 of CLRS for a diagram and description of adjacency list representations of graphs)10 points CLRS 93-9: Professor Olay is consulting for an oil company, which is planning a large pipelinerunning each to west through an oil field of n wells The company whats to connect a spur pipeline from eachwell directly to the main pipeline along a shortest route (either north or south), as shown in Figure 92 in thetextbook Given the x- and y-coordinates of the wells, how should the professor pick the optimal location of themain pipeline, which would be the one that minimizes the total length of the spurs? Show how to determinethe optimal location in linear time, and prove the correctness and linear bound of the algorithm40 points Collaborative Problem–CLRS 5-1: With a b-bit counter, we can ordinarily only count up to 2b − 1With R Morris’s probabilistic counting, we can count up to a much larger value at the expense of some loss ofprecisionWe let a counter value i represent a count of nifor i = 0, 1,, 2b−1, where the niform an increasing sequenceof nonnegative values We assume that the initial value of the counter is 0, representing a count of n0 = 0The Increment options works on a counter containing the value i in a probabilistic manner If i = 2b − 1, thenthe operator reports an overflow error Otherwise, the Increment operator increases the counter by 1 withprobabilities 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 weselect, say, ni = 2i−1for i > 0 or ni = Fi (the ith Fibonacci number–See Section 32 in the text)For this problem, assume that n2b−1is 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 havebeen performed is exactly n(b) 20 points The analysis of the variance of the count represented by the counter depends on the sequenceof the ni Let us consider a simple case: ni = 100i for all i ≥ 0 Determine the variance in the valuerepresented by the register after n Increment operations have been performed30 points Collaborative Problem– In this problem we consider two stacks A and B manipulated using thefollowing 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 beenmoved or A is empty1Assume that A and B are implemented using doubly-linked lists such the P ushA and P ushB, as well as asingle 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 amortizedrunning time O(1)