Solved–Assignment 2:– Heap, sort and search– Solution

Description

In this and all following assignments, follow the same general instructions as given in Assignment 1. Always remember to justify your answers by giving your analysis.

1. (20pts, Problem A-1.10 in the Goodrich textbook, Page 49)

Given an array A of n integers, find the longest subarray of A such that all the numbers in that subarray are in sorted order. Give your pseudo code. What is the running time of your method?

2. (10 pts) What are the minimum and maximum number of elements in a heap of height h?

3. (15 pts) Show the max-heap that results from building the heap directly on the following integer values in an array: 10, 5, 12, 3, 2, 1, 8, 7, 9, 4.

4. (15 pts) Show how heapsort works in-place using the max-heap built in the previous question to sort the values in ascending order.

5. (20pts) Assuming that the pivot is always the 2nd element of a list, simulate the execution of Quicksort on the following input: 32, 23, 18, 27, 8, 30, 98, 14, 45, 0, 99, 47, 43, 23, 123, 75, 6, 19, 85.

6. (20pts) Consider the following extension to binary search on a sorted array A for an item x: Let A[p] and A[q] be the partitioning elements of A so that A is divided into three roughly equal-sized lists (i.e., a difference of 1 or 2 is allowed between the sizes of these sublists but no more). Based on A[p] and A[q], decide the sublist where x may exist. Repeat this process until the sublist is small enough that the answer can be directly obtained.

• Write pseudo-code for the above TernarySearch method, specifying all the parameters correctly.

• Derive the recurrence relation for the running time of the TernarySearch algorithm.

• Solve the recurrence relation, find a close-bound for the running time of TernarySearch and then express this close-bound using asymptotic notation. Justify your answer.

• Derive an expression and its asymptotic bound for the space complexity of TernarySearch.

Prepare your answers in a Word or PDF file and submit to e-learning.