Skip to content
Solved Assignments

Analysis of Algorithms: Heapification, Minimum Spanning Tree, Inversions, Sorting, and Random-Select

This paper analyzes key algorithms in computer science, including heapification, minimum spanning trees, and sorting techniques.

Preview 3 of 8 pages

See the first 3 pages exactly as they appear in the document.

  1. Page 1
    Read page 1 as text

    Analysis of Algorithms: Heapification, Minimum Spanning Tree, Inversions, Sorting, and Random - Select Problem 1: Answer: The provided solution will not heapify the given array. The HeapifyHeap() function can be considered as building a heap from the bottom up, consecutively pushing downward to establish the property of the heap. The algorithm for the supporting function HeapifyHeap() is given below: Algorithm alter_heapify(array, arraySize) is Input : An array array and its size arraySize. Ouput : A bubble down array. Assign the index in array of the last parent node to the variable begin. The index of the last parent node will be equal to (arraySize - 2 ) / 2. // assign value i ← (arraySize - 2 ) / 2 With the help of a while loop push down the node at index begin to the proper place such that all nodes below the index begin are in heap order. // create while loop while i ≥ 0 do // call PushDown() PushDown(array, begin, arraySize - 1) // decrement begin i ← i – 1 After pushing down the root, all the elements will be in heap order. Thus, now the bubble down array is heapify. An example to show this is as given below:

  2. Page 2
  3. Page 3
    Read page 3 as text

    Problem 2: a) What is the length of minimum spanning tree in Figure 1? Answer: The given figure shows that there are six nodes. Thus, the minimum length will be n - 1. So, here it will be 6 - 1=5. So, the minimum length of this spanning tree is 5. b) Assume an algorithm A solves the minimum spanning tree problem. Prove that A has a time complexity of Ω (n log n). Answer: The total number of the comparisons required in the worst case for finding the largest path from a given minimum spanning tree of the desired leave is ( ) ( ) log N!  . The given expression can be evaluated using the Stirling formula ( ) N 1 N! 2 N N / 1 N e O      = +         The value of the expression after evaluation is as given below: ( ) ( ) ( ) log N! NlogN  =  So, the value of the lower bound after expanding is ( ) Nlog N  . Thus, it can be said that the algorithm will have time complexity of ( ) Nlog N  . For example, A minimum spanning tree algorithm such as Prim - Jarnik’s algorithm can be used to find a solution for calculating the cost of traveling salesman with a slight modification. Instead of

5 more pages in the full document

Unlock it once and it stays in your library, ready to chat with or turn into flashcards.

Unlock the full document

More Information Technology study materials

See all

Study this document with CramX

Once it is in your library, every tool can work from it.