Problem (a): Find minimum j for each element of a given array
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[.]
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[.]
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.
Problem (b): Find minimum A[j] for each element of a given array
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[.]
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
j←i+1
while j
if A[j]>A[i] then
result[z] ← j
z ← z+1
break
j ← j+1
END
i ← i+1
END
return result[.]
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
Order an Essay Now & Get These Features For Free:
Turnitin Report
Formatting
Title Page
Citation
Outline
