Overview / Logistics

This is an individual assignment, so you may not speak with anyone else in the class as you work through this.

Learning Objectives

• Design a data structure from scratch to efficiently realize an ADT
• Analyze the time complexity of a data structure
• Design tests to convince yourself of correctness

Background

In this assignment, you will implement a data structure to realize a "RandomToggleSet" ADT. I had to solve this problem myself last summer when I was implementing The Concatenator. We want to maintain a set of objects and to choose random items from this set, but we want to "toggle" (enable/disable) certain elements from being chosen. Specifically, this ADT has three methods:

• add(element): A void method that adds an element, toggling it to True. If the element is already in the set, don't add it twice, but toggle it to True if it isn't already.
• toggle(element): A void method that toggles whether an element can be selected or not. Specifically, if the element is in the set and is False, change it to True. If the element is in the set and is True, change it to False. If the element is not in the set, you should throw an exception.
• sample(): Select and return an element uniformly at random from among the elements that are set to True.

You can assume that all of the elements are hashable if that helps. As an example, suppose we made the following method calls:

• myset.add("c")
• myset.add("s")
• myset.toggle("c")
• myset.add(2)
• myset.add(7)
• myset.toggle(7)
• myset.add(7)
• myset.add(1)
• myset.toggle(2)

Then the following picture shows a depiction of what's in the set, where green indicates that this element is available to be selected and red indicates this item is not available to be selected (note that the items are in no particular order, and you don't have to maintain them in any particular order in your data structure)

Then, let's suppose we called sample 100 times. Here's an example of what we might see:

7 7 1 1 s 7 s 1 s s 7 s s s s s 7 1 s 7 7 s 7 s s s 7 s s 7 7 7 1 7 s s 7 1 1 s 7 1 1 7 7 s 1 1 s 7 7 7 7 1 1 1 s 7 1 7 7 s 1 7 s s s 7 1 1 1 7 1 s 7 1 s 1 s s s 1 s 1 7 s 1 1 1 7 1 7 7 7 7 s 1 7 s s

Any sequence including s, 7, and 1 is possible, but if this is working properly, there's a much higher chance that they will be evenly distributed. In this example, we've drawn s 36 times, 7 35 times, and 1 29 times.

Getting Started/Rubric

Click here to view a skeleton of the ADT that you can start with. To complete this, feel free to use any of the code from prior assignments, modules, or class exercises. But take some time to plan things out and to bounce several ideas around before you start coding. It's okay if your first ideas aren't the most efficient as you get a sense for the problem, but you should keep trying to improve the runtime as much as you can before you start coding.

Below is how points will be allocated on this assignment:

Correctness of Implementation (15 Points)

The data structure you create correctly implements the ADT to the specification above

Efficiency (10 Points)

The data structure you create implements all operations efficiently. Note that it is possible to implement all three operations in O(1) amortized time with the right data structure, but you will get a lot of partial credit for other reasonably efficient implementations (e.g. O(log(N)) for certain operations).

Formal Analysis of Runtime (6 Points)

Explain what the worst case runtime of each method is, using big-O notation. Provide a brief explanation as to why. Even if your data structure isn't as efficient as it could be, you will get full credit for correctly analyzing it.

NOTE: If you used a hash table (including use of python's set and dictionary classes), you can assume the worst case time of its operations is O(1) (even though it is technically O(N))

Testing (5 Points)

Write a brief test to demonstrate that your data structure is working properly. It should be more interesting and comprehensive than the example I gave above.