Description

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