AVL Tree, Set Intersection Algorithms, Sloppy Inc. Communication, Array Search

1. Consider the data sequence S = [82, 91, 13, 92, 64, 10, 28, 55, 96, 97]. Draw a valid AVL tree for it,
assuming that the data has arrived one at the time. Show detailed steps by giving the AVL tree
after inserting each element.
Solution :

2. Consider two sets of integers, X = [x1, x2, . . . , xn] and Y = [y1, y2, . . . , yn]. Write two versions of a
FindSetIntersection(X, Y ) algorithm to find the common elements in both sets. Each of your
algorithms should return an array with the common elements, or an empty array if there are no
common elements.
You may make use of any algorithm introduced in the lectures to help you develop your That is, you
do not have to write the ‘standard’ algorithms – just use them. Therefore, you should be able to write
each algorithm in about 0 lines of code. You must include appropriate comments in your pseudocode.
(a) Write a pre-sorting based algorithm of FindSetIntersection(X, Y). Your algorithm should strictly run in
O (n log n).
Solution: Use arbitrary array Z of length minimum(n , m). Where n is the length of array X and m is the
length of array Y. Now sorting both the arrays X and Y. Take 2 pointers say i and j pointing to the 0th
index of arrays X and Y. Compare X[i] and Y[j]. If both are equal then z[k] = X[i], and increment I, j and k.
else if X[i] < Y[j] then increment i. else increment j. In the end we would get intersection of both the
arrays in Z. The overall complexity of algorithm is (maximum (nlogn , mlogm) + (m+n)) => (nlogn).
function FindSetIntersection(X[.], Y[.])
//input has 2 arrays say X and Y of integers having length n and m
//presorting both the arrays using Quick Sort
//i is an integer in the range 0 to n
//j is an integer in the range 0 to m
While i < n and j < m do
if X[i] = Y[j] then
Z[k] ← X[i]
k ← k+1 //increment k
i ← i+1 //increment i
j ← j+1 //increment j
else if X[i] < Y[j] then
i ← i+1 //increment i
else if X[i] > Y[j] then
j ← j+1 //increment j
END
return Z[.]

(b) Write a Hashing based algorithm of FindSetIntersection(X, Y). Your algorithm should run in O(n).
Solution:
Initialize an empty Hashset say hs. Initially loop through the array X and insert all the elements from X to
Hashset hs. Now loop through the array Y and check whether the elements of array Y exist in Hashset hs
or not. If exist then add element from Y to the output array Z. Time complexity of this algorithm is
Θ(m+n) where n is the length of array X and m is the length of array Y. under the assumption that hash
set search and insert operations take Θ(1) time.
function FindSetIntersection(X[.], Y[.])
// initialize empty hashset h.
// input has 2 arrays say X and Y of integers having length n and m
for each element x in X
h ← x
for each element y in Y
if h contains y then
Z ← y //store y in Z
END
return Z[.]