Description

1 Problem 1 (25 points)
1.1 Problem 1.1 (10 points)
Suppose we wish not only to increment a counter of length m ∈ N but also to reset it to zero (i.e., make all bits in it 0). Counting the time to examine or modify a bit as Θ(1), show how to implement INCREMENT and RESET operations on a counter (represented as an array of bits) so that any sequence of n operations takes O(1) amortized time per operation.
Prove correctness and running time of your algorithms.
(Hint: Keep a pointer to the highest-order 1.)
1.2 Problem 1.2 (15 points)
Design a data structure to support the following two operations for a set S of integers, which allows duplicate values:
• INSERT(S,x) inserts x into S.
• DELETE-LARGER-HALF(S) deletes the largest d|S|/2e elements from
S.
Explain how to implement this data structure so that any sequence of m INSERT and DELETE-LARGER-HALF operations runs in amortized O(1) time per operation. Your implementation should also include a way to output the elements of S in O(|S|) time.
Prove the running time of your implementation.
2 Problem 2 (10 points)
Let G = (V,E) be a directed graph. a ∈ V is a central vertex if for all b ∈ V there exists a path from a to b. Provide an O(|V | + |E|) time algorithm to test whether graph G has a central vertex.
Prove the correctness of your algorithm and analyze the running time.
3 Problem 3 (15 points)
You’re helping some analysts monitor a collection of networked computers, tracking the spread of fake information. There are n computers in the system, labeled C1,C2,…,Cn, and as input you’re given a collection of trace data indicating the times at which pairs of computers communicated. Thus the data is a sequence of ordered triples (Ci,Cj,tk); such a triple indicates that Ci and Cj exchanged bits at time tk. There are m triples total.
We’ll assume that the triples are presented to you in sorted order of time. For purposes of simplicity, we’ll assume that each pair of computers communicates at most once during the interval you’re observing. The analysts you’re working with would like to be able to answer questions of the following form: If the fake information was generated by computer Ca at time x, could it possibly have been sent to Cb by time y? The mechanics of communicating the information are simple: if a computer containing the fake information Ci communicates with another computer Cj that hasn’t received that information yet by time tk (in other words, if one of the triples (Ci,Cj,tk) or (Ci,Cj,tk) appears in the trace data), then computer Cj receives the fake information, starting at time tk.
The fake information can thus spread from one machine to another across a sequence of communications, provided that no step in this sequence involves a move backward in time. Thus, for example, if Ci has received the fake information by time tk, and the trace data contains triples (Ci,Cj,tk) and (Cj,Cq,tr), where tk ≤ tr, then Cq will receive the fake information via Cj. (Note that it is okay for tk to be equal to tr; this would mean that Cj had open connections to both Ci and Cq at the same time, and so the information would have been sent from Ci to Cq.)
Design an algorithm that answers questions of this type: given a collection of trace data, the algorithm should decide whether the fake information generated by computer Ca at time x could have been received by computer Cb by time y. The algorithm should run in time O(m + n).
Prove correctness and running time as usual.