School of Computing and Information Systems
COMP90038 Algorithms and Complexity Tutorial Week 6
27–31 August 2018
Plan
Keep up with the exercises; make sure you tackle them all—some of them in your own time, if
needed. Question 41 is optional, for those who want to convince themselves, formally, that log n
grows faster than log log n. In an exam, you will not be asked to formally prove statements like
that; however, you will be assumed to know that
√
n grows faster than log n, which in turn grows
faster than log log n, and so on.
The exercises
33. Write an algorithm to classify all edges of an undirected graph, so that depth-first tree edges
can be distinguished from back edges.
34. Show how the algorithm from the previous question can be utilised to decide whether an
undirected graph is cyclic.
35. Explain how one could also use breadth-first search to see whether an undirected graph is
cyclic. Which of the two traversals, depth-first and breadth-first, will be able to find cycles
faster? (If there is no clear winner, give an example where one is better, and another example
where the other is better.)
36. Design an algorithm to check whether an undirected graph is 2-colourable, that is, whether
its nodes can be coloured with just two colours in such a way that no edge connects two nodes
of the same colour. Hint: Adapt one of the graph traversal algorithms.
37. Apply the DFS-based topsort algorithm to linearize the following graph:
a b c
d e
f g
38. Apply insertion sort to the list S, O, R, T, X, A, M, P, L, E.
39. For what kind of array is the time complexity of insertion sort linear?
40. Trace how interpolation search proceeds when searching for 42 in an array containing (in
index positions 0..21)
20, 20, 21, 23, 25, 26, 26, 27, 29, 29, 29, 30, 32, 33, 34, 36, 38, 40, 41, 43, 43, 45
41. (Optional) For evenly distributed keys, interpolation search is O(log log n). Show that log log n
has a slower rate of growth than log n. Hint: Differential calculus tells us that (log x)′ = Θ( 1
x
)
and the chain rule says that (f ◦ g)′(x) = f ′(g(x))g′(x).