Compsci 100, Fall 2009, Sets

You can work with other students in answering questions. 

Name: _____________________  Netid: _________________
 
Name: _____________________  Netid: _________________

Name: _____________________  Netid: _________________
These questions refer to the set code here which provides BST, AVL, and Trie set implementations as well as Hash and standard java.util implementations. The questions below are about some of the implementations: SortedArraySet, BSTSet, and TrieSet (briefly).

  1. What Java language feature in the interface ISimpleSet ensures that elements of a set can be iterated over using the enhanced for-loop syntax, e.g., ISimpleSet<String> set = new BSTSet<String>(); // code here to add elements to the set for(String s : set) { // process each element }
  2. What Java-isms/language-notation in both BSTSet and SortedArraySet indicates that only objects that are mutually comparable can be stored in these sets, just as is the case for TreeSetSet, for example.
  3. What line of code in BSTSet.add ensures that duplicate elements will not be stored in the set?
  4. Describe in words what happens when a tree consisting of one element has that element removed and where that happens in the code of private, helper method BSTSet.remove.
  5. What is the name of the methods that help make implementing th inner class TreeIterator straightforward?
  6. Which one line in SortedArraySet has the potential to take the longest time to execute, why?
  7. What two lines (by number) in TrieSet ensure that the size of the set is adjusted appropriately when elements are either added or removed?