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).