COMP90038 Algorithms and Complexity Assignment 2 Solution - 2018

This document provides solutions to a COMP90038 Algorithms and Complexity assignment. The first problem involves constructing a valid AVL tree from a given data sequence, demonstrating the insertion steps. The second problem presents two FindSetIntersection algorithms: one based on pre-sorting (O(n log n) complexity) and the other utilizing hashing (O(n) complexity). The third problem addresses an employee communication scenario at Sloppy Inc., requiring the design of an efficient algorithm (with time complexity analysis) to determine the minimum number of days for decision dissemination in a hierarchical structure represented as an n-ary tree. The final problem involves array manipulation, specifically finding the minimum j such that A[j] > A[i] and j > i, with solutions provided for both O(n^2) and O(n log n) complexities. The solution utilizes AVL trees and inorder successor to find the required element.

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[.]
3. Sloppy Inc. has a very unusual way to communicate the decisions made by its CEO to all employees.

Each day, any employee that knows the decision can disclose it to at most one of its direct
subordinates. Design an efficient algorithm to compute the minimum number of days required for the
decision to be disclosed to all employees. What is the time complexity of your algorithm?
To help you design your algorithm, assume that Sloppy Inc. has a hierarchical structure resembling an
n ary tree. Each employee is labeled {0, 1, . . . , n − 1}, where 0 corresponds to root of the tree (the
CEO). To store the tree you can use a two-dimensional array C [n] [n], where k = C [i] [0] is the number
of direct subordinates of employee i, and C [i] [1 . . . k] contains the labels of each direct subordinate
employee. Any other entry in the array has value of −1. Note that the order in which the messages are
distributed matters, e.g., employees with deeper subordinate trees should probably receive the
message first.
Solution:
Consider 2 queue q1 and q2 that can store the edge by starting and ending point of the edge, initialize
the q1 by inserting the 0th node I.e CEO (0,0) and the resulting complexity will be in Θ(n2) as we will
check each and every element from the table and each edge will be processed in the Queue.
Struct Edge
{
int start
int end;
int height;
}
function computeNumberOfDays(C[.][.], 0)
// Compute the height for each and every node(employee)and store in the array height
height[.] ← computeHeight(C[.][.])
i ← 1
index ← 0
h ← 0
days ← 1
While i < C[0][0] do
If C[0][i] not equals -1 && h<height[i] then
index ← i
h ← height[i]
i ← i+1
END
If index not equals 0 then
C[0][index] ← -1
q1.insert(0, C[0][C[0][i]])
days ← 1
While (q1 is not empty) or (q2 is not empty) do

While (q1 is not Empty) do
Edge e ← q1.delete()
i ← 1
index ← 0
h ← 0
While i < C[e.start][0] do
If C[e.start][i] not equals -1
&& h<height[C[e.start][i]] then
index ← i
h ← height[i]
i ← i+1
END
If index not equals 0 then
q2.insert(e.start, C[e.start][index])
C[e.start][index] ← -1
i←1
index ← 0
h ← 0
while i<C[e.end][0] do
If C[e.end][i] not equals -1
&& h<height[C[e.end][i]] then
index ← i
h ← height[i]
i ← i+1
END
If index not equals 0 then
q2.insert(e.end, C[e.end][index])
C[e.end][index] ← -1
days ← days+1
END
While q2 is not empty do
Edge e ← q2.delete()
i ← 1
index ← 0
h ← 0
While i < C[e.start][0] do
if C[e.start][i] not equals -1
&& h<height[C[e.start][i]] then
index ← i
h ← height[i]
i ← i+1
END
If index not equals 0 then
q1.insert(e.start, C[e.start][index])
C[e.start][index] ← -1

i←1
index ← 0
h ← 0
while i<C[e.end][0] do
If C[e.end][i] not equals -1
&& h<height[C[e.end][i]] then
index ← i
h ← height[i]
i ← i+1
END
If index not equals 0 then
q1.insert(e.end, C[e.end][index])
C[e.end][index] ← -1
days ← days+1
END
END
if days ← 0 then
return 0
else
return days-1
// height[.] is an array of size n
function computeHeight(C[.][.], int index)
i ← 1
h = 0
while i<C[index][0] do
If C[index][i] not equal -1 then
computeHeight(C[.][.], C[index][i] )
h ← Max(h, height[C[index][i]])
height[index] ← h+1
Break
END
return height[.]
4. Given an array of n numbers A [0 . . . n − 1]. Write an efficient algorithm for below cases:

(a) [3 Marks] For each of the element A [i], find the minimum j so that A [j] > A [i] and j > i. Your algorithm
should return an array of length n. If such j does not exist for some i, that entry should be -1. What is
the complexity of your algorithm?
Solution: Search the maximum element A[j] for the element A[j] with minimum j, if there is no such A[j]
then set result[z]=-1 otherwise set the result[z] with the j. the resulting complexity will still be in Θ(n2).
function searchMinimumJ(A[.])
result[.] {-1} //result is the output array of length n
Z ← 0 // index of the output array
length ← A.length()
i ← 0
while i<length do
j←i+1
while j<length do
if A[j]>A[i] then
result[z] ← j
z ← z+1
break
j ← j+1
END
i ← i+1
END
return result[.]
(b) For each of the element A [i], find the minimum A [j] so that A [j] > A [i] and j > i. Your algorithm
should return an array of length n. If such j does not exist for some i, that entry should be -1. Your
algorithm should have O (n log n) complexity.
Solution: Create an AVL tree for the given Array inserting elements in the given order. The Structure of
AVL tree Node will contain 5 parameters node data, left child, right child pointer, height and index in
array location.
Now for every element from input array do the following steps. Find the element in AVL tree, next find
its inorder successor, store the index of inorder successor in output array. Now delete the current
element from ALV tree. Repeat the above steps till last element of given array.
// create structure for tree Node as

struct Node
{
int data; // stores the element values
Struct Node *left; // pointer to left node
Struct Node *right; // pointer to right node
Int height; // height of tree node
Int index; // index of element from the input array
};
function searchMinimumAj (A [.])
//Input is an array of length n
//output array result[.]
createAVLTree(A[.]) //creates the AVL tree for the given array A[.]
root ← A[0]
for every element x from A[0…n]
key ← searchElement(root , x)
// find inorder successor for the key
index ← findIndexOfInOrderSucessor(root, key)
// store the index of inorder successor for key
result[z] = index
z ← z+1 // increment z
// delete the key from the AVL tree
deleteKey(root , key)
END
return result[.]
function searchElement(root , key)
// root denotes the root of the AVL tree
// Key is the node data that has to be found
while root is not NULL
if key = root.data then
return root
else if key > root.data
root ← root.right
else
root ← root.left
end while
return root
end

function findIndexOfInOrderSucessor(root , key)
// root denotes the root of the AVL tree
// Key is the node data that has to be found
// if right subtree of key node is not null then find the smallest element in right subtree
if key.right not NULL then
return minValue(key.right)
//successor node initialized as null
succ = NULL;
//starting from the root node and searching for successor in subtrees
while root not NULL do
if key.data < root.data then
succ ← root
root ← root.left
else if key.data > root.data then
root ← root.right
else
break;
END while
return succ.index
END