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 logn grows faster than loglogn. 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 logn, which in turn grows faster than loglogn, 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:
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(loglogn). Show that loglogn has a slower rate of growth than logn. Hint: Differential calculus tells us that (logx)′ = Θ(x1) and the chain rule says that (f ◦ g)′(x) = f′(g(x))g′(x).
