Test #1

Question 1

What should you know about optimally sorting 5 elements

Answer 1

1. We can sort 5 items with 7 comparisons.
2. Merge sort requires 8 comparisons to sort 5 items. Since we can sort 5 items with 7 comparisons, this means that merge sort is not optimal if we count exact comparisons.
3. The lower bound on comparison sorting for n = 5 is 7 comparisons. Since we can sort 5 items with 7 comparisons, this is the best possible lower bound for sorting 5 items.

Question 2

Any comparison-based algorithm for sorting a list of size n must perform at least _____ comparisons in the worst case.

Answer 2

Ω(n log n)

Question 3

Any comparison-based algorithm for sorting a list of size n must perform at least ___ comparisons in the worst case.

Answer 3

Ceil(log(n!))

Question 4

What is worst-case time for quick-sort?

Answer 4

O(n²)

Question 5

What is worst-case time for insertion sort?

Answer 5

O(n2)

Question 6

What is worst-case time for merge sort?

Answer 6

O(n log n)

Question 7

What is worst-case time for heap sort?

Answer 7

O(n log n)

Question 8

What is the storage requirement for Insertion sort?

Answer 8

In place

Question 9

What is the storage requirement for quick sort?

Answer 9

O(log n) extra for stack

Question 10

What is the storage requirement for heap sort?

Answer 10

In-place

Question 11

What is Quick Sort expected time?

Answer 11

O(n log n)

Question 12

When is insertion sort good?

Answer 12

Good when input is almost sorted

Question 13

A priority queue need to minimally support the following operations…

Answer 13

Insert an item w a given key

Delete an item

Select the item with the most urgent priority in the priority queue

Question 14

What is totla time of SiftUp helper function for binary heaps?

Answer 14

at most 1 comparison on each level, so total time is O(log n)

Question 15

What is total time of SiftDown helper function for binary heaps?

Answer 15

At most 2 comparisons at each level, so the total time is O(log n)

Question 16

Total time of Binary Heap Insertion?

Answer 16

Sift time dominates, so total time is O(log n)

Question 17

Total time for Binary Heap Deletion?

Answer 17

Sift up/down time dominates, so total time is O(log n)

Question 18

Extract Max binary heap total time?

Answer 18

Delete time dominates, so total time is O(log n)

Question 19

What is the recurrence equatuion and asymptoic analysis for Merge Sort?

Answer 19