Written Assignment #7: Practice Final Exam (make-up points only)

Due: before class on May 13th

(Note: each 5 points on this practice exam can replace one missed point on other written assignments - thus this assignment can replace up to 30 points total)

  1. Data Structure Design: (30 pts) Your task is to implement a representation of a railroad map. You have cities with names and locations, listed as (X,Y) coordinates, and railroad links between cities, with each link having a distance between those cities. The operations that will be performed most frequently (and therefore which must be performed quickly) are finding the nearest city to a given point (set of X,Y coordinates), and finding the shortest path from one city to another, traversing the rail lines.

    1. (10 pts) Write a data structure for this task as a C, Pascal, or C++ structure/record.
    2. (5 pts) Justify your selection in part (a). Contrast with at least one alternative organization.
    3. (10 pts) Write an algorithm for finding the nearest city to a given point, using your data structure.
    4. (5 pts) What is the complexity of your algorithm in part (c)? Give your answer using big O notation, and tell whether you are providing worst or average case, and absolute or amortized values.

  2. Data Structure Selection (15 pts - 5 each) Given that you have a set of records, each having a unique integer key value, which data structure would you use to maintain these records, given the following sets of circumstances? Explain your answer.
    1. The most frequent operations are finding whether a record with a particular key value is in the database, and finding the record with the key value which is the immediate predecessor or immediate successor of a given key value..
    2. You have frequent insertions and deletions, as well as the above operations.

    3. Suppose you must find not just the immediate predecessor or successor, but the n closest key values (from a value that might or might not be in the database) (assume that insertions or deletions are very rare, once the database has been set up).

  3. (15 pts) Grow a B-tree of order 4 (i.e., a 2-3-4 tree), with the following sequence of key values:
    1 15 10 4 8 9 5 2 7.
  4. (5 points) Show a corresponding red-black tree for the B-tree of problem 3.

  5. Hashing (25 pts. - 5 each) Given a hash-table of size 7, and the hash function: h(k)=x mod 7, and the following sequence of data items: 1, 10, 2, 15, 16.

    1. Show the resulting hash table using separate chaining.
    2. Show the results using in-place chaining.
    3. Show the results using linear probing.
    4. Show the results using double hashing. Assume the following secondary hash function:
      g(x) = x mod 6.
    5. given the table resulting in part (d), add the value 8, using Brent's algorithm.

  6. Point data (60 pts. - 5 each) Given the following sequence of point data insertions: A(10,10), B(6,15), C(12,14), D(5,7), E(14,6), F(5,12), G(8,11), H(17,16), I(11,10).

    1. Show the inverted list structure for this data.
    2. Show the grid method, assuming values range from 0 to 20, and grids of size 4x4.
    3. Show the point quad-tree resulting from this data (show the tree structure, clearly labeling which child is which).
    4. Show the MX-quadtree for this data.
    5. Show the PR-quadtree for this data.
    6. Show the K-D Tree for this data.
    7. Show the Excell method for this data, assuming a bucket size of 2.
    8. Show the bit-interleaved values for these points counting X as the most significant.
    9. Show the results of linear hashing on these points, using as hash function:
      tex2html_wrap_inline106 = k mod tex2html_wrap_inline106, where k is the bit-interleaved value computed in part (h)
    10. Show the results of order-preserving linear hashing, assuming the hash function:
      tex2html_wrap_inline106 = (reverse k) mod tex2html_wrap_inline106, where the key value for a point is the bit-interleaved value, computed in part (h).
    11. show the 2-d range tree for this data.
    12. show the range priority tree for this data.