Fundamental Algorithms
Homework #9

Due Apr. 12

  1. a. Insert the keys below, in their given order, into a 2-3 tree. Show the intermediary steps and the resulting tree.

    2,15, 8, 10, 6, 5, 4.

    b. Remove key 10 from the resulting tree in (a) above.

  2. Consider a tree (any tree) with n leaves and m internal (non-leaf) vertices. Let li be the distance of leaf i from the root and let wj be the nomber of leaves in the subtree rooted at the j-th internal vertex. Prove: Sum over the leaves of li = sum over the internal vertices of wj

  3. Consider the following hashing method. We use 2 hashing functions: h1(k)=3*k modulo p , p is an odd prime. h2(k)= (sum of digits of k) modulo p +1, same p as in h1. Given up to p keys we reserve p+1 contiguous locations in memory an then process the keys one by one as follows. For i from 1 to number of keys insert ki into location h1(ki) provided that the location is not occupied. If it is occupied then insert ki into location h2(ki).

    a. How would you retrieve a key from a hashed list as above?

    b. What is the complexity of insertion and retrieval?

    c. Can the procedure fail to hash all the given keys into different locations? If yes then suggest a solution.

    d. Assume p = 13. Apply the above procedure to the list of keys below. Show the result of the hashing method above applied to the list. 25, 81, 75, 13, 65, 72, 88.

  4. Consider the undirected graph with vertices {A,B,C,D,E,F} and edges: {A-B, B-C, C-D, D-E, E-F, F-A, F-B, B-E, E-C }.

    a. Draw the Graph.

    b. Show the adjacency matrix of the graph.

    c. Represent the graph by the adjacency lists of it's vertices.

    d. Are the lists in (c) unique?

    e. Show a DFS of the graph.

    f. Show a BFS of the graph.

    g. Do the searches in (e) and (f) above depend on (c) above. If yes in what way?