Description
1 1 Convex Hull The Convex Hull of a set P of n points in x-y plane is a minimum subset Q of points in P such that all points in P can be generated by a convex combination of points in Q. In other words, the points in Q are corners of the convex-polygon of smallest area that encloses all the points in P. Design an O(n log n) time Divide-and-Conquer algorithm to compute the convex hull of a set P of n input points {(x1, y1), (x2, y2), . . . , (xn, yn)}. [15 marks] Hint: Step 1: Split P into sets P1 and P2 of size dn/2e by diving along median of x-coordinate of all the points. Step 2: Recursively compute convex hull of sets P1 and P2. Step 3: Finally combine convex hull of P1 and P2 in linear time to obtain convex hull of P. 2 2 Particle Interaction Some physicists are working on interactions among large numbers of very small charged particles. Basically, their set-up works as follows. They have an inert lattice structure, and they use this for placing charged particles at regular spacing along a straight line. Thus we can model their structure as consisting of the points {1, 2, 3, …, n} on the real line; and at each of these points j, they have a particle with charge qj . (Each charge can be either positive or negative.) They want to study the total force on each particle, by measuring it and then comparing it to a computational prediction. This computational part is where they need your help. The total net force on particle j, by Coulomb’s Law, is equal to Fj = X ij C qi qj (j − i) 2 . They have written the following simple program to compute Fj , for all j. 1 for j = 1, 2, …, n do 2 Initialize Fj to 0; 3 for i = 1, 2, …, n do 4 if i < j then 5 Add C qi qj (j−i) 2 to Fj ; 6 else if i > j then 7 Add − C qi qj (j−i) 2 to Fj ; 8 end 9 end 10 Output Fj ; 11 end The running time of this program is O(n 2 ). Your task is to design an algorithm that computes all the forces Fj in O(n log n) time. [15 marks] 3 Distance computation using Matrix Multiplication Let G = (V, E) be an unweighted undirected graph, and H = (V, EH) be a undirected graph obtained from G that satisfy: (x, y) ∈ EH if and only if (x, y) ∈ E or there exists a w ∈ V such that (x, w),(w, y) ∈ E. Further, let DG denote the distance-matrix of G, and DH be the distance-matrix of H. (a) Prove that the graph H = (V, EH) can be computed from G in O(n ω ) time, where ω is the exponent of matrix-multiplication. [2 marks] (b) Argue that for any x, y ∈ V , DH(x, y) = lDG(x, y) 2 m . [2 marks] 3 (c) Let AG be adjacency matrix of G, and M = DH ∗ AG. Prove that for any x, y ∈ V , the following holds. [8 marks] DG(x, y) = ( 2DH(x, y) M(x, y) ≥ degreeG(y) · DH(x, y) 2DH(x, y) − 1 M(x, y) degreeG(y) · DH(x, y) (d) Use (c) to argue that DG is computable from DH in O(n ω ) time. [1 marks] (e) Prove that all-pairs-distances in n-vertex unweighted undirected graph can be computed in O(n ω log n) time, if ω is larger than two. [2 marks] 4 Universal Hashing Let U = [0, M − 1] be a universe of M elements, p be a prime number in range [M, 2M], and n(<< M) be an integer. Consider the following hash functions (where r ∈ [1, p − 1]): H(x) := (x) mod n Hr(x) := ((rx) mod p) mod n (a) Compute a random set S as follows: − Intialize S to empty. − Repeat n times: choose a random integer in U and add it to S. Prove the following. [7 marks] P rob(max-chain-length in hash table of S under hash-function H(·) > log2 n) 6 1 n (b) Prove that for any given r ∈ [1, p − 1], there exists at least M/nCn subsets of U of size n in which maximum chain length in hash-table corresponding to Hr(x) is Θ(n). [3 marks] (c) Implement H() and Hr() in Python/Java for M = 104 and the following different choices of sets of size n = 100: For k ∈ [1, n], Sk is union of {0, n, 2n, 3n, . . . , (k − 1)n} and n − k random elements in U. Obtain a plot of Max-chain-length for hash functions H(), Hr() over different choices of sets Sk defined above. Note that you must choose a different random r for each choice of Sk. Provide a justification for your plots. [5 marks] 4