Description
1) Show the red-black trees that result after successively inserting the keys 41, 38, 31, 12, 19, 8
into an initially empty red-black tree. [CLRS 13.3-2]
10 points
2) Rewrite the procedure DFS, using a stack to eliminate recursion. [CLRS 22.3-7]
15 points
3) Design an efficient algorithm that gets a graph G(V,E) and returns “yes” if it is possible to have
an Eulerian tour in G. Otherwise it returns “no”.
15 points
4) Assume that in each node of a graph an integer value has been stored. Design an efficient
algorithm that given a graph G(V,E) and value X returns true if X is in G. Otherwise returns false.
10 points
