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.

Week 6 (Q10–Q12):
Q10 Apply Dijkstra’s algorithm on the graph represented by the following
adjacency matrix to find the shortest distances and the shortest paths from
vertex 1 to the other vertices. Show the contents of arrays S, d and π after each
iteration of the while loop.
 
1 2 3 4 5
1 0 4 2 6 8 
 
2 ∞ 0 ∞ 4 3 
vertex 
 
3 ∞ ∞ 0 1 ∞

4 ∞ 1 ∞ 0 3 
5 ∞ ∞ ∞ ∞ 0

Q11 Let G = (V, E, W ) be a weighted graph, and let s and z be distinct

Q12 Dijkstra’s algorithm requires that the input graph has all edges being
non-negative. Give an example where Dijkstra’s algorithm does not work cor-
rectly with negative weights.

Optional 4 Implement Dijkstra’s and use it to verify your solution on Q10.

Week 7 (Q13–Q14):
Q13 Run topological sort on the following DAG. Give the list of sorted nodes

Figure 1: DAG for Q13. When there are multiple choices of nodes to visit, visit
them in alphabetical order

3
Q14 For the DAG given in Q13, there are multiple valid linearizations. For in-
stance, [C,H,D,B,E,F,G,A] is a valid linearization, and so is [C,D,H,B,G,A,E,F].
What is the total number of valid linearizations for this DAG?
a) Write code to count the numbers of valid linearizations by enumerating
all possible ways (all permutations) to sort the nodes, then check if the sort
results in a valid linearization.
b) Formulate the counting problem as a graph traversal (hint: look up lecture
nodes on 8-queens formulation). Define the new graph structure (hint: it is
a tree called a “search tree”). What are the nodes? What are the edges?
What is the root node? Then use graph traversal to count the number of valid
linearizations.
c) What is the runtime for a), what is the runtime for b)? What makes b)
more efficient than a)?

Week 8 (Q15–Q16 ):

Figure 2: plot for Week 8

Q15 Run by hand Prim’s algorithm for finding minimum spanning tree (MST)
on the graph above, starting from vertex G. Show the contents of arrays S, d
and pi after each iteration of the while loop when a vertex is added to the MST.

Q16 Now run by hand Kruskal’s algorithm on the same graph (with the
weighted QuickUnion algorithm for Union-Find). Show the contents of arrays
id and sz at each step when an edge is added to the MST.