Data Structures Homework

Due Friday February 2, 2018 5pm

  1. We have seen how dynamic arrays enable arrays to grow while still achieving constant-time amortized performance. This problem concerns extending dynamic arrays to let them both grow and shrink on demand.

    • Consider an underflow strategy that cuts the array size in half whenever the array falls below half full. Give an example sequence of insertions and deletions where this strategy gives a bad amortized cost.
    • Then, give a better underflow strategy than that suggested above, one that achieves constant amortized cost per deletion.
  2. A hypothetical concatenate operation takes two sets S1 and S2, where every key in S1 is smaller than any key in S2, and merges them together. Give an algorithm to concatenate two binary search trees into one binary search tree. The worst-case running time should be O(h), where h is the maximal height of the two trees. Implement this in Python to concatenate trees of IP addresses like we built in lab. In order to create trees that have this property of being ordered relative to each other, you will need to modify the dataset you're using to build the trees, either manually or by changing the gen_ip.py script. (Examples of the insert and search functions have been uploaded to the lab's github repo, linked on the course page.)

  3. Implement versions of several different dictionary data structures, such as linked lists, binary trees, balanced binary search trees, and hash tables. Conduct experiments to assess the relative performance of these data structures in a simple application that reads a large text file and reports exactly one instance of each word that appears within it. This application can be efficiently implemented by maintaining a dictionary of all distinct words that have appeared thus far in the text and inserting/reporting each word that is not found. Write a few paragraphs with your conclusions.

  4. Write a program to print a binary tree using preorder, inorder, and postorder traversal. With your submission, include your test cases. Feel free to use code from Monday's lab to build and test your program.

Submit your homework via email to sastrand@pdx.edu as a single PDF before Friday February 2nd at 5pm.