Homework #2 Solution



  1. In class we gave an algorithm for nding the closest pair of points on the plane. The notion of distance we used was Euclidean distance: d((x; y); (x0 ; y0 )) = p(x x0 )2 + (y y0 )2. Show how you can adapt the algorithm to nd the closest pair for a di erent notion of

distance. Speci cally, give an algorithm with run-time O(n log n) for the following problem. Given a set of points P = fp1; : : : ; png in the plane, nd a pair of points with the smallest possible L1-distance among the points where L1-distance between two points is de ned by d1((x; y); (x0 ; y0 )) = jx x0 j + jy y0 j.

For full-credit your algorithm should be correct and you should explain why your algorithm works. In particular, if your algorithm is similar to what we did in class, you need to prove the analogue of the main lemma (one that allowed us to look only 15 distances ahead for Euclidean distance) we did in class. [.75 points]

  1. An array A[0; 1; : : : ; n 1] is said to have a majority element if more than half of its elements are the same. Given an array, the task is to design an e cient algorithm to tell whether the array has a majority element, and, if so, to nd that element. The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form \is A[i] > A[j]?”. (Think of the array elements as mp3 les, say; so in particular, you cannot sort the elements.) However you can answer questions of the form: \is A[i] = A[j]” in constant time.

Give an algorithm to solve the problem. For full-credit, your algorithm should run in time O(n log n) and you need to bound the time-complexity of the algorithm. (You don’t have to

prove correctness.) [.75 points]

(Hint: Split the array A into two arrays AL and AR of half the size each. Does knowing the majority elements of AL and AR help you gure out the majority element of A? If so, you can use a divide-and-conquer approach.)

  1. Run the BFS algorithm for the following graph with s = 1 and t = 9: G = (V; E), where V =

f1; 2; 3; 4; 5; 6; 7; 8; 9g, and E = ff1; 2g; f1; 3g; f2; 3g; f2; 4g; f2; 5g; f3; 5g; f3; 7g; f4; 5g; f5; 6g; f8; 9gg. Your work should the step-by-step evolution of the lists L0; L1; ::: and of the array DISCOV ERED as we did in class (cf. the transcript uploaded in the calendar). [.75 points]

  1. Given a graph G = (V; E) in adjacency list representation, give an algorithm that runs in

time O(jV j jEj) to check if G has a ‘triangle’, i.e., a triple of distinct vertices fu; v; wg such that all three edges between them are present in G. [.75 points]

Additional Problems. DO NOT turn in answers for the following problems – they are meant for your curiosity and understanding.

  1. Problems 3.9, 3.11 from textbook [KT].

  1. Problem 3.16 from Chapter 3 of [DPV].