1) Define, what do the following notations mean: (1 + 1 p)
a) T(n) = O(f(n))
b) T(n) = 0(g(n)) (pallo, jossa on "rusetti" keskellä sisällä)
where T(n) is the run time of an algorithm and f(n) and g(n) are functions.
c) The analytical results of the run time of an algorithm are commonly presented using the Big Oh' notation. Explain shortly what are the most important problems of this notation when it is usea for comparing the run time of different algorithms.
2)Solve the recurrence T(N) = T(N / 2) + N^2, when N is s power of two and T(1) = 1. Write also the intermediate phases of your solution. (4p)
3) a) Define the data structure heap. (lp)
b) Store the characters E X A M I N A T I O N in this order into a heap. Draw the contents of the heap as a tree after each insertion. (3p)
c) Remove four topmost items from the heap and present the heap as a tree after each removal. (2p)
4) a) Explain two methods for implementing a self-organizing list. (2p)
b) Explain what is the basic idea of hashing. What are the two basic mechanishms needed for implementing a hashing method? Present one hashing algorithm and explain how these basic mechanisms are implemented in it. (4p)
5) a) What problem can be solved by Union-Find-algorithm? (lp)
b) Draw a union-find forest for a graph that has nodes A..L and edges
AB, AC, BD, CD, GH, GJ, IH, IL, CE, DF, EF, KJ, KL, ID.
Add the edges to the forest in this order. The final forest is a sufficient answer. (3p).
c) What is meant by height-balancing in Union-Find-algorithm? (lp)
d) What is meant by path compression in Union-Find-algorithm? (lp)