Final Exam Review


Answer the Questions from the Review Sheets For Midterms 1 & 2. In addition:



Heaps

  • What is the Max Heap Property? How does it differ from the BST property?
  • What is the Big-O runtime of each of the heap algorithms we discussed in class?
  • Trace each step of the buildMaxHeap operation (diagram and array) on the following:

Diagram                    Array

                       

                        A = [4, 9, 7, 18, 2, 3]

1.






2.                        A = [ ___ , ___, ___, ___, ___, ___ ]   







           

3.                        A = [ ___ , ___, ___, ___, ___, ___ ]   







4.                        A = [ ___ , ___, ___, ___, ___, ___ ]   







  • Trace heapInsert on the below Max Heap and the value 35. Show diagram and array at each step below:


Diagram                    Array

                       

1.                        A = [21, 11, 13, 2, 9]







2.                        A = [ ___ , ___, ___, ___, ___, ___ ]   






           

3.                        A = [ ___ , ___, ___, ___, ___, ___  ]   







4.                        A = [ ___ , ___, ___, ___, ___, ___  ]   




  • Trace heapSort on the following heap. Show diagram and array at each step below:

Diagram                    Array

                       

1.                        A = [100, 90, 80, 70]







2.                        A = [ ___ , ___, ___, ___ ]   






           

3.                        A = [ ___ , ___, ___, ___ ]   







4.                        A = [ ___ , ___, ___, ___ ]   







5.                        A = [ ___ , ___, ___, ___ ]   





Trace the merge sort algorithm on the following array of values:


[50, 2, 12, 17, 6, 1, 4, 52]


[ ___, ___, ___, ___ ] [ ___, ___, ___, ___ ]



[ ___, ___ ]    [ ___, ___]   [ ___, ___] [ ___, ___ ]



[ ___ ]    [ ___ ] [ ___ ]    [ ___ ] [ ___ ]    [ ___ ] [ ___ ]    [ ___ ]



[ ___, ___ ]    [ ___, ___]   [ ___, ___] [ ___, ___ ]



[ ___, ___, ___, ___ ] [ ___, ___, ___, ___ ]



[ ___, ___, ___, ___, ___, ___, ___, ___ ]



Write the pseudocode for the mergeSort operation. Note that you do not need to write the helper function merge.


mergeSort(A, low, high)







What is the Big O run-time of MergeSort in the best, worst and average case?


Best: O (                            )



Average: O (                            )



Worst: O (                            )



Give an example of a sorting algorithm that we have studied in this class that falls into each of the following categories:


An in-place sorting algorithm:


A comparison-based sorting algorithm:


A divide-and-conquer sorting algorithm:


A parallel sorting algorithm: