(b) Input: A sorted array A of n integers.

Output: Elements x, y ∈ A such |x 一 y| is maximum.

(c) Input: An unsorted array A of n integers.

Output: Elements x, y ∈ A such |x 一 y| is minimum.

(d) Input: A sorted array A of n integers.

Output: Elements x, y ∈ A such |x 一 y| is minimum.

3.  (25 points) An array A with n entries is said to have a majority element if more than half of its entries are the same.  Given A, we want to find such a majority element, if one exists. A question of the form  “Is A[i] = A[j]?” can be answered in constant time; however questions of the form  “Is A[i] > A[j]?” are not permitted (for example, the elements of the array could be images so there is no order among them).

Design an efficient algorithm to solve this problem in Θ(n log n) time.

4.  (28 points) Consider a complete undirected binary tree T on n = 2d  一 1 nodes, for some integer d > 1. Each node v in T is labeled with a real number xv; all xv  are distinct. A node v in T is a local minimum if its label xv  is less than the label xu  for every node u joined to v by an edge.

You are given such a complete binary tree T but the labeling is only specified in the following implicit way: for each node v, you can determine xv  by probing the node v. Give an efficient algorithm to find a local minimum of T.  (You may assume that each probe takes constant time.)

5.  (30 points) You’re helping some security analysts monitor a collection of networked comput- ers tracking the spread of an online virus.  There are n computers in the system, labelled C1, C2 , . . . , Cn. You are given a trace indicating the times at which pairs of computers com- municated. The trace consists of m triples (Ci, Cj, tk); such a triple indicates that Ci  and Cj communicated at time tk.  At this time, a virus could have spread from Ci  to Cj  (and vice versa).

We assume that the trace holds the triples sorted by time.  For simplicity, we assume that each pair of computers communicate at most once over the time of the trace.  Also, it is possible to have pairs (Ci, Cj, tk) and (Ci, Ce, tk); this would indicate that Ci  communicated with both Cj  and Ce  at time tk  allowing a virus to spread in any way among the 3 machines.

We would like to answer questions of the following form: If a virus was introduced at Ci  at time x, could it have spread to Cj  at time y? That is, is there a sequence of communications that could have led from the virus moving from Ci  to Cj?

Design an algorithm that, given as input a collection of (sorted) trace data and a virus query, gives a yes/no answer to the query. The algorithm should run in time O(m + n).

6.  (25 points) Give an efficient algorithm that takes as input a directed graph G = (V, E) and determines whether or not there is a vertex s ∈ V from which all other vertices are reachable.

RECOMMENDED EXERCISES: Do NOT submit, they will not be graded. Solutions to the first three exercises will be provided.

1.  Give tight asymptotic bounds for the following recurrences.

● T (n) = 4T (n/2) + n3 一 1.

● T (n) = 8T (n/2) + n2 .

● T (n) = 6T (n/3) + n.

● T (n) = T ( ′n) + 1.

2.  Show that, if λ is a positive real number, then f(n) = 1 + λ + λ2 + . . . + λn  is

(a)  Θ(1) if λ < 1.

(b)  Θ(n) if λ = 1.

(c)  Θ(λn ) if λ > 1.

Therefore, in big-Θ notation, the sum of a geometric series is simply the first term if the series is strictly decreasing, the last term if the series is strictly increasing, or the number of terms if the series is unchanging.

3. In the table below, indicate the relationship between functions f and g for each pair (f, g) by writing “yes” or “no” in each box. For example, if f = O(g) then write “yes” in the first box. Here logb x = (log2 x)b .