COMP90038: Hashing based Algorithm of FindSetUnion - IT Assignment Help

Assignment Task:

Objectives 

To improve your understanding of the time complexity of 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 

1. [4 Marks] Consider two sets of integers represented in arrays, X = [x1, x2, . . . , xn] and Y = [y1, y2, . . . , yn]. Write two versions of a FindSetUnion(X, Y ) algorithm to find the union of X and Y as an array. An element is in the union of X and Y if it appears in at least one of X and Y . 

You may make use 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. 

(a) [2 Marks] Write a pre-sorting based algorithm of FindSetUnion(X, Y ). Your algorithm should strictly run in O (n log n). 

(b) [2 Marks] Write a Hashing based algorithm of FindSetUnion(X, Y ). Your algorithm should run in O (n). 

2. [12 Marks] A web is a data structure similar to a heap that can be used to implement the priority queue ADT. As with a heap, a web is defined by two properties: 

• Structural property: A web W consists of l levels, l ≥ 0. The ith level, for 0 ≤ i < l, contains at most i + 1 entries, indicated as Wi,j for 0 ≤ j ≤ i. All levels but the last are completely filled, and the last level is left-justified. 

• Ordering property: Any node Wi,j has at most two children: Wi+1,j and Wi+1,j+1, if those nodes exits. The priority of a node is always greater than or equal to the priority of either child node. 

(a) [1+2+2+2 = 7 Marks] A web W with n nodes can be stored in an array A of size n, similarly to an array-based heap. So, for example, if n ≥ 1, the top of the web W0,0 will be stored at A[0]. Give formulas for the array index that the following web entires will have, justifying how you arrived at these conclusions. Assume the n, i and j are such that all indicated web nodes actually exist. 

i [1 Mark] Wi,j 

ii [2 Marks] Left and right children of Wi,j 

iii [2 Marks] Left and right parents of Wi,j 

iv [2 Marks] Left and right children of the node corresponding to A[k] 

(b) [2 Marks] Give upper and lower bounds for the number of nodes n in a web W with l levels, where l ≥ 1. For example, a web with 2 levels has at least 2 and at most 3 nodes. Make your bounds as tight as possible. Briefly justify your answer. 

(c) [3 marks] Briefly describe an efficient algorithm to eject the maximal element from the web W that is stored in an array A of size n. Find the complexity of this algorithm and justify your conclusion Note: you do not have to write this algorithm in pseudocode. We are expecting that you write a short paragraph or a short list of bullet points describing the important steps of the algorithm and explaining the time complexity. 

3. [14 Marks] Researchers from the School of BioSciences have requested our help with one of their experiments. They are performing behavioural experiments with zebrafish. At any one instance in time there are a large number of zebrafish in the aquarium. For their particular experiment, the biologist take a snapshot of the aquarium and then need to find the longest series of zebrafish such the length of each fish along the horizontal direction in the aquarium is increasing. They also need to know the number of zebra fish in this series. 

For example, the snapshot of the aquarium resulted in fish lengths of [2, 5, 3, 7, 11, 1, 12, 4, 15, 14, 6, 16]. One possible longest series of increasing lengths in this case is [2, 3, 7, 11, 12, 14, 16] with 7 zebrafish. We say one possible longest series of increasing lengths here because it is not necessarily unique. For example, the length 14 in the output could be replaced with 15: [2, 3, 7, 11, 12, 15, 16] and also be valid. 

In this question you will consider algorithms for finding the longest series of increasing lengths via the function LongestIncreasingLengths(A[0, · · · , n − 1]), as well as the size of this output array.

This COMP90038: IT Assignment has been solved by our IT Experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.

Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.