Data Structures And Algorithms For Sorting And Search

To improve your understanding of data structures and algorithms for sorting and search. To consolidate your knowledge of trees and tree-based algorithms. To develop problem-solving and design skills. To develop skills in analysis and formal reasoning about complex concepts. To improve written communication skills; in particular the ability to use pseudo-code and present algorithms clearly, precisely and unambiguously.

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.

2. Consider two sets of integers, X = [x₁; x₂; : : : ; x_n] and Y = [y₁; y₂; : : : ; y_n]. Write two versions of a FindSetIntersection(X; Y ) algorithm to nd 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 solution. 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 10 lines of code. You must include appropriate comments in your pseudocode.

• Write a pre-sorting based algorithm of FindSetIntersection(X; Y ). Your algorithm should strictly run in O (n log n).
• Write a Hashing based algorithm of FindSetIntersection(X; Y ). Your algorithm should run in O (n).

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 e cient 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 f0; 1; : : : ; n 1g, 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 rst.

4. Given an array of n numbers A [0 : : : n 1]. Write an e  cient algorithm for below cases:

(a) For each of the element A [i], fifind 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?

(b) For each of the element A [i], fifind 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.

To help you verify your algorithm, for the sequence [80; 19; 49; 45; 65; 71; 76; 28; 68; 66] the results are:

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 Θ(n²) 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 Θ(n²).

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