COMP90038 Algorithms and Complexity: Understanding of Data Structures
Questions:
Objectives
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.
Problems
- 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.
- Consider two sets of integers, X = [x1; x2; : : : ; xn] and Y = [y1; y2; : : : ; yn]. 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).
- 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.
- 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:
Answers:
1.
2.
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[.])
//inpu
t 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[.]
2.(b)
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.
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. (a)
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[.]
4. (b)
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
Buy COMP90038 Algorithms and Complexity: Understanding of Data Structures Answers Online
Talk to our expert to get the help with COMP90038 Algorithms and Complexity: Understanding of Data Structures Answers to complete your assessment on time and boost your grades now
The main aim/motive of the management assignment help services is to get connect with a greater number of students, and effectively help, and support them in getting completing their assignments the students also get find this a wonderful opportunity where they could effectively learn more about their topics, as the experts also have the best team members with them in which all the members effectively support each other to get complete their diploma assignments. They complete the assessments of the students in an appropriate manner and deliver them back to the students before the due date of the assignment so that the students could timely submit this, and can score higher marks. The experts of the assignment help services at urgenthomework.com are so much skilled, capable, talented, and experienced in their field of programming homework help writing assignments, so, for this, they can effectively write the best economics assignment help services.
