SC2001 Tutorials
Solutions to all problems will be given on the course website a week after
the problems are posted. For questions specifically on the optional problems,
please come to Evans’ office hour (do not bother the tutorial tutors about them).
Week 3 (Q1–Q3):
Q1 The worst case for Insertion Sort occurs when the keys are initially in
decreasing order. Suppose the performance of Insertion Sort is measured by the
total number of comparisons between array elements (not counting the number
of swaps). Show at least two other initial arrangements of keys that are also
worst cases for Insertion Sort.
Q2 Use the divide and conquer approach to design an algorithm that finds
both the largest and the smallest elements in an array of n integers. Show that
your algorithm does at most roughly 1.5n comparisons of the elements. Assume
n = 2k .
Q3 Show how Merge Sort sorts each of the arrays below and give the number
of comparisons among array elements in sorting each array.
(a) 14 40 31 28 3 15 17 51
(b) 23 23 23 23 23 23 23 23
Optional 1 Implement code for insertion sort and merge sort, and count the
numbers of comparisons on their inputs. Empirically validate your answers for
question Q1 and Q3.
Week 4 (Q4–Q6):
Q4 Suppose that, instead of using E[middle] as pivot, Quick Sort also can use
the median of E[first], E[(first+last)/2] and E[last]. How many key comparisons
will Quick Sort do in the worst case to sort n elements? (Remember to count
the comparisons done in choosing the pivot.)
Q5 Each of n elements in an array may have one of the key values red, white,
or blue. Give an efficient algorithm for rearranging the elements so that all the
reds come before all the whites, and all the whites come before all the blues.
(It may happen that there are no elements of one or two of the colours.) The
1
only operations permitted on the elements are examination of a key to find out
what colour it is, and a swap, or interchange, of two elements (specified by their
indices). What is the asymptotic order of the worst case running time of your
algorithm? (There is a linear-time solution.)
Q6 Suppose we have an unsorted array A of n elements and we want to know
if the array contains any duplicate elements.
(a) Outline (clearly) an efficient method for solving this problem.
(b) What is the asymptotic order of the running time of your method in the
worst case? Justify your answer.
(c) Suppose we know the n elements are integers from the range 1, . . . , 2n, so
other operations besides comparing keys may be done. Give an algorithm
for the same problem that is specialized to use this information. Tell the
asymptotic order of the worst case running time for this solution. It should
be of lower order than your solution for part (a).
Optional 2 Implement code for quick sort, and track the numbers of com-
parisons it makes on an input. Consider all possible inputs from the set of
permutations of [1, 2, 3, 4, 5, 6, 7] (there are a total of 7! of such inputs)
Of the 7! inputs, how many would result in the maximum number of com-
parisons on quicksort? How many would result in the minimum number of
comparisons? What about the average case?
Answer these questions empirically (by writing code).
Week 5 (Q7–Q9):
Q7 Given an array with content (type date): 1 Jul, 30 Jan, 22 Mar, 22 Dec,
30 May, 21 Feb, 3 Nov, 7 Jun, 22 Feb, 21 Nov, 30 Dec; all of the same year.
Suppose an earlier date is considered bigger than a later date; for example, “30
Jan” is bigger than “30 Dec”. In order to sort these dates by Heap Sort, we
first construct a maximizing heap. Show the content of the array after the heap
construction phase.
Q8 An array of distinct keys in decreasing order is to be sorted (into increas-
ing order) by Heap Sort.
(a) How many comparisons of keys are done in the heap construction phase
(Algorithm constructHeap() / heapify() ) if there are 10 elements?
(b) How many are done if there are n elements? Show how you derive your
answer.
(c) Is an array in decreasing order the best case, the worst case, or an interme-
diate case for this algorithm? Justify your answer.
Q9 Given k lists with a total of n numbers, where k ≥ 2 and each list has
been sorted in decreasing order, design an algorithm to merge the k lists into
one list sorted in decreasing order, with running time O(n log2 k).
2
Optional 3 Implement heapify / heapsort and track the numbers of compar-
isons and swaps. Validate your answer to Q7 and Q8 with it.