Homework #5 Introduction to Algorithms

Homework #5
Introduction to Algorithms
601.433/633

Where to submit: On Gradescope, please mark the pages for each question
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.
You may assume that the counter is initially zero and that you may access and
modify any specific bit (say bit j ∈ [m]) in O(1) time. Additionally, you may
assume that the total count in the counter never exceeds 2
m − 1 during the course
of the n operations.
Prove correctness and running time of your algorithms.
(Hint: Keep a pointer to the highest-order 1.)
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
2
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.
3