Exercise 6 Theory: Methods of sorting

Exercise 1:

a) What is the running time of the most effective algorithm which can figure if all elements in an unsorted list with n elements are unique?

1) Theta(1)
2) O(log n)
3) O(n)
4) O(n * log n)
5) O(n^2)
6) O(n^2 * log n)
7) O(2^n)
8) O(n!)

b) How many times do you have to execute a search in an unsorted list of n = 10^3 elements before sorting the list and then doing a binary search
would be preferable to a sequential search? We are assuming that the soring algorithm used is mergesort.

1) 2
2) 4
3) 6
4) 8
5) 10
6) 12
7) 14

c) What if we have 10^5 elements?

1) 4
2) 8
3) 12
4) 16
5) 20
6) 24
7) 28

Exercise 2:

a) If it is expensive to write to memory you would prefer 

1) Bubblesort
2) Selectionsort
3) Insertion sort
4) It does not matter

b) If we know that we are treating integers, a sorting method based on comparison will be able to achieve O(n) running time.

1) True
2) False

c) If we already have made a heap of the numbers which we wish to sort, we can sort with Heapsort with running time O(n).

1) True
2) False

d) Quicksort uses O(1) extra memory in addition to what is needed to store the numbers to be sorted.

1) True
2) False

e) Mergesort uses O(lg n) extra memory in addition to what is needed to store the numbers to be sorted.

1) True
2) False

f) If you know that n numbers in the intervall [0, n-1] (with duplicates) is going to be sorted, counting sort is a good algorithm.

1) True
2) False

g) The reason that Radix-sort has to be started on the least-significant-digit, is that the later sortings have larger influence on the final order.

1) True
2) False

h) All input can give worst-case running time for randomized-quicksort.

1) True
2) False

i) Best-case running time for insertionsort is O(n).

1) True
2) False

j) If you replace the linear search in insertionsort with a binary search you will get an O(n * lg n) searching algorithm.

1) True
2) False

Exercise 3:

a) Here follows four examples of binary trees.

(figure)

Which of these satisfy the requirements of a max-heap?

1) A and B
2) A and C
3) A and D
4) B and C
5) B and D
6) C and D
7) All of them
8) None of them

b) If we have a heap looking like this:

(figure)

How does the list represetning the heap look after we have done three iterations of heap sort?

1) 21, 14, 12, 11, 9, 8, 4
2) 11, 8, 9, 4, 12, 14, 21
3) 11, 9, 4, 8, 12, 14, 21
4) 11, 9, 8, 4, 12, 14, 21

c) Is heapsort a stable sorting algorithm?

1) Yes
2) No

Exercise 4:

Lars Jakob (Norwegian name) works in Posten Norge (Norwegian post terminal) and is sorting letters aimed at every corner of the world. Like all workers in
Posten Norge with respect for themselves, he uses radix-sort to find out where the letters are going. He has ten boxes where he temporary store letters
(numbered 0 to 9) until they are completely sorted. Letters are sorted by zip-code. He gets an unusual big load of ten letters and immediately starts
to sort these. The letters are going to (in order)
2307, 4284, 0327, 4296, 3281, 2291, 8771, 1434, 9215, 4301

a) After one iteration of sorting, how many letters are in box 1?

1) 3
2) 4
3) 5
4) 6

b) If Lars Jakob takes out the letters after 2 iterations of sorting, which order do the letters have (given that he takes them out first
from box 1, then box 2 and so on)?

1) 2307, 4284, 0327, 4301, 8771, 1434, 3281, 9215, 2291, 4296
2) 8771, 2291, 4284, 4296, 2307, 4301, 1434, 3281, 0327, 9215
3) 4301, 2307, 9215, 0327, 1434, 8771, 3281, 4284, 2291, 4296
4) 9215, 3281, 4284, 2291, 4296, 4301, 2307, 0327, 1434, 8771

c) After 3 iterations of sorting, what order will the letters in box 2 lie in?

1) 2291, 3281, 4284, 4296, 9215
2) 2291, 9215, 4296, 3281, 4284
3) 9215, 4296, 3281, 2291, 4284
4) 9215, 3281, 4284, 2291, 4296
5) 3281, 4284, 2291, 9251, 4296