Introduction to Data Structures CS106 Spring 2013

Lab 3: Efficient Representation of Sets

Check out the sets_sorted project files for Lab 3. This contains an additional file, which is the answer key for Lab 2, with information about the complexities of the operations. In the file you will be modifying class Set again, this time creating a set representation based on a sorted vector (Python list) that still contains no duplicates. The very idea of sorting depends on being able to have a consistent ordering of elements, so of course this representation will limit uses of the set class to only sets of elements that can be compared with < and > (as well as ==, which was of course needed for the previous representation, and the very idea of a set). While we usually try to ensure that changes to representation don't affect the use of a type, you are allowed to violate this rule in this way for this lab. (You are invited to think about how you would create a set type that checked, when each item is added, to see whether or not it is compatible with the types of items in the sorted array, and if not, simply revert to the unsorted representation for that particular let this is, however, beyond what you should actually try to program in this course).

The specific requirements for this lab are:

When these are done, add a README.txt file discussing the advantages of the new representation, from the point of a user (when would the new version work better? when (if ever) would the old one have been preferable?), and a README-DESIGN.txt file to serve as a guide for other programmers working on your class. Then use Team->Commit to hand in your work (and, of course, you can also use commit to make backups also at each significant milestone, e.g., at the end of each bullet item above).