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.

(20pts, Problem A1.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?

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

(15 pts) Show the maxheap 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.

(15 pts) Show how heapsort works inplace using the maxheap built in the previous question to sort the values in ascending order.

(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.

(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 equalsized 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 pseudocode 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 closebound for the running time of TernarySearch and then express this closebound 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 elearning.