$30.00
Description

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); (x^{0} ; y^{0} )) = ^{p}(x x^{0} )^{2} + (y y^{0} )^{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 runtime O(n log n) for the following problem. Given a set of points P = fp_{1}; : : : ; p_{n}g in the plane, nd a pair of points with the smallest possible L1distance among the points where L1distance between two points is de ned by d_{1}((x; y); (x^{0} ; y^{0} )) = jx x^{0} j + jy y^{0} j.
For fullcredit 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]

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 fullcredit, your algorithm should run in time O(n log n) and you need to bound the timecomplexity of the algorithm. (You don’t have to
prove correctness.) [.75 points]
(Hint: Split the array A into two arrays A_{L} and A_{R} of half the size each. Does knowing the majority elements of A_{L} and A_{R} help you gure out the majority element of A? If so, you can use a divideandconquer approach.)

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 stepbystep evolution of the lists L_{0}; L_{1}; ::: and of the array DISCOV ERED as we did in class (cf. the transcript uploaded in the calendar). [.75 points]

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.

Problems 3.9, 3.11 from textbook [KT].

Problem 3.16 from Chapter 3 of [DPV].