Question

1.)

(a) There exists a very popular sorting algorithm called Timsort, the default sorting algorithm in both Python and Java. This sort is a combination of two different sorting algorithms: Merge sort, and Insertion sort. Recall that the Big-O of Merge sort is O(nlogn) and the Big-O of Insertion sort is O(n 2 ). What advantage would Timsort have to combine the two algorithms if merge-sort has a better Big-O metric?

(b) Consider two algorithms: f(n) and g(n). You run both algorithms with an input n = 10, 000. You find that f(n) takes 10 ms while g(n) takes 1 min to run. Which of these has a better (i.e. smaller) Big-O metric?

2.)You are given 9 identical looking balls and told that one of them is slightly heavier than the others. Your task is to identify the defective ball. All you have is a balanced scale that can tell you which of two balls is heavier.

(a) Show how to identify the heavier ball in just 2 weighings.

(b) Justify why it is not possible to determine the defective ball in fewer than 2 weighings

Answer 1

1)

a) This is because for small values of n insertion sort runs faster than merge sort . Hence insertion sort can be used to Optimize merge sort. Hence, for smaller values of n, Timesort would give better results than merge sort.

b) f(n) has a smaller Big O metric since it takes lesser time than g(n) for the same input size.

2)

a)

Let label the balls as A, B, C, D, E, F, G, H, I.

1. Weigh ABC versus DEF.

Scenario a: If these (1) balance, then we know the oddball is one of G, H, I.

          2. Weigh G versus H.

          Scenario a.i: If these (2) balance, the oddball is I.

          Scenario a.ii: If these (2) do not balance, the heavier one is the oddball.

Scenario b: If these (1) do not balance, then the oddball is on the heavier side. For simplicity, assume the ABC side is heavier, so the oddball is one of A, B, C.

          2. Weigh A versus B.

          Scenario b.i: If these (2) balance, the oddball is C.

          Scenario b.ii: If these (2) do not balance, the heavier one is the oddball.

b) It is impossible to find the heavier ball in 1 attempt because we need 1 attempt to find the subset of balls which contains the heavier ball.