CMSC 351

Big THETA of sorts

100

Name 3 sorts with average case BigTheta (n^2) or BigTheta (n log n)

Insertion,selection,Bubble (n^2)

Heap, merge, quick

200

Big theta of merge sort in the worse case

n log n

(Same answer for all cases)

300

Best bigTheta we can get for comparison based sorting algorithim in the worst case

n log n

Merge Sort or Heap sort

400

Name the two sorts that have the same big Theta for all cases. Then which is faster

Selection and Merge sort

Selection BigTheta(n^2)

Merge BigTheta(n log n)

500

Name the 3 sorts that have best case of Big theta (n)

Bubble, Selection, Insertion, Heap, Merge, Quick

Heap, Bubble, Insertion

heap sort

100

Method you call after deleting the root node

Heapify

200

What are the requirements for a complete binary tree

Every level except the last one is completely filled and the last level is filled from left to right

300

Difference between max heap and min heap

For max heap the nodes value is greater than its 2 child while for min heap the nodes value is less than its 2 children

400

what is the height of a binary tree when you know the number of nodes

log(n+1) - 1

merge sort

100

Is merge sort stable T/F

True

200

Does merge sort use an auxiliary array T/F

True

Quick sort

100

Position of pivot according to sudo code given in slides

Last element

200

What will the value of t be after a partition

The location of the pivot would be swapped with or the first number that is strictly greater than the pivot (you swap if the pivot is equal to the number)

Master Theorem

100

If c < log_b a then what case are we in

Case 1

200

T(n) = 16T (n/4) + n

Case 1

BigTheta(n^2)

300

T(n) = 2T (n/2) + n log n

Case 2

BigTheta (n (log n)^2)

400

T(n) = 64T(n/4) + nn^1/2 log n

Case 2 Fancy

Big Theta( n^3/2(log n)^2 )

500

What is the answer

T(n) = 6T (n/3) + n^2 log n

Case 3

Big Theta (n^2 log n)