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