Heaps

a$)$ Using a Heap data structure, and the Push and Pop operations on the heap, tell me in words, how

would you sort a list of integers? $20$ pts$?$

$5)$ Using the figure $($below$),$

a$)$ List the steps the Dijkstra Algorithm will take to find the distance from A to E$?20$ pts

b$)$ What is the distance from A to E according to the Dijkstra Algorithm? $20$ pts

$6)$ For the sequence $8,9,5,7,0,2,3,1,6,4,40$ pt $($Note: you don$$t have to sort this data to get the answers$)$

An $$inversion$$ is any pair that is in the wrong order. They don$$t have to be next to each other.

a$)$ How many inversions are there in the above sequence? $($List them$)$

b$)$ How many inversions are there if you exchange the $9$ and the $1$ in the sequence?

$($This is the new sequence $8,1,5,7,0,2,3,9,6,4)?$

c$)$ What is the maximum number of inversions in a reverse sorted $($worst case$)$ sequence of N numbers? $($This

question is not related to parts a and b$.$ N is a variable and can have any positive value $>=2,$ so give me the

answer in terms of N$).($Suggestion: Try a few sequences to see if your answer makes sense$)$

$7)$ A simplified B$-$Tree like we studied in this class has $32$ keys at the top level $($m $=32).($This tree has no root:

the top level is level $1$ and it has $32$ keys$).$ The B$-$tree has $2$ million leaves at the bottom level. Each key has

$32$ child keys at the next level and each of those has $32$ child keys at the next level and so on$.$ How many levels

are in the tree? Hint: Remember leaves are only at the bottom level of the tree, and the # of leaves $=$ # of keys

at the bottom level. Suggestion: Check your answer to see if it makes sense. $40$ pts$.$

$8)$ Given the recurrence relationship: T$(1)=1$ and T$($N$)=2$T$($N$/2)+$ N

a$)$ Show that T$($N$)=4$T$($N$/4)+2$N $10$ pts $($use the method on bottom half of page $308$ the $4$rth edition text,

or page $278$ in $3$rd edition$)$

b$)$ Show T$($N$)=8$T$($N$/8)+3$N $10$ pts

c$)$ Let N $=32,$ let k $=$ log$2($N$)=5$; what does T equal? $($Hint$.$ Plug the numbers in to the formula and compute$)$

$5$ pts

$9.$ Find the Median of Three $($aka M$3)$ of this sequence $20$ pts $\{25,43,67,18,11,21,60\}.$

Remember, the M$3$ has to be one of the data points. Show your work!