Question: Model 2 The Java Set API It turns out that the notion of a mathematical set is very useful in computer science. Often times we
Model 2 The Java Set API
It turns out that the notion of a mathematical set is very useful in computer science. Often times we only care if an element is in the set or not, and we don't really care about an ordering or how many copies there are.
We've listed Java's Set API above. Your first thought might be "huh, this looks a lot like the List API", and you wouldn't be wrong! In fact, the main difference is that we no longer have any methods that care about the indices of elements. And this makes sense, because the mathematical set is an unordered list of items.
Questions (5 min) Questions about Java's Set API
Read the documentation for the retainAll(), removeAll(), containsAll(), size(), and addAll() methods in Java's Set API (or use your knowledge of lists to guess what each does). Each of these corresponds to one of the set operations and relations detailed in Model 1, Parts 2 and 3. For example, the addAll() method corresponds to the union operation.
Which of these corresponds to the intersection operation?
Which of these corresponds to the cardinality operation?
Which of these corresponds to the set difference operation?
Which of these corresponds to the subset relation?
If A = {1,2,3} and B = {4,5,6} then A B = {1,2,3,4,5,6} and A and B remain unchanged. However, for Java sets s1 and s2, s1.addAll(s2) updates s1. Why might Java's designers have decided to make s1.addAll(s2) alter s1 instead of providing a s1.union(s2) method which creates a third set, leaving s1 and s2 unaltered?
So, you might ask, Sets just seem strictly worse than Lists, right? Lists can do everything that Sets can do, and more!
Well to answer this, we have an Eclipse project for you to run! Download the project from here and load it into Eclipse. Then, run the main method in the timing.TimerDriver class. This will create some graphs and output some CSV files. The graphs should pop up on your screen, but if you exit out of them, they will be saved as jpegs in the root of the project.
After running the TimerDriver, answer the following questions for each of the operations: add, contains, remove.
Questions (15 min) Questions about contains
Paste the generated graph from contains-times.jpeg here
What is the relationship between each successive tick-mark along both the x-axis and the y-axis? That is, do they grow linearly or exponentially?
Describe the difference in running times between list.remove() and set.remove() as the number of iterations increase.
What do you suppose causes this difference in behavior?
Questions about remove
Paste the generated graph from remove-times.jpeg here
What is the relationship between each successive tick-mark along both the x-axis and the y-axis? That is, do they grow linearly or exponentially?
Describe the difference in running times between list.remove() and set.remove() as the number of iterations increase.
What do you suppose causes this difference in behavior?
Questions about add
Paste the generated graph from add-times.jpeg here
What is the relationship between each successive tick-mark along both the x-axis and the y-axis? That is, do they grow linearly or exponentially?
Relate the running times between list.add() and set.add() as the number of iterations increase. How does this relation compare with the contains and remove methods?
Suppose you had to keep track of registered users by their user names. You want to
Add new users by their user name
Remove users that unsubscribe from your service
Look up usernames to see if they already exist
Would you rather use a Set or a List to do this? Why?
Suppose you are running a customer service website and you want to track when customers first submit their help request. You want to ensure that customers are helped in the order that they arrive at your site. You want to
Add new customers, keeping track of which customers arrived before which other customers
Remove customers after they have been helped
Only store their contact information (so no time data is stored---we have to keep track of the order they arrive in our data structure!)
Would you rather use a List or a Set? If a Set, why? If a List, would you rather use an ArrayList, a SinglyLinkedList, or a DoublyLinkedList? Why?
All Methods Modifier and Type boolearn Instance Methods Abstract Methods Default Methods Method and Description add (E e) Adds the specified element to this set if it is not already present (optional operation) addAll (Collection extends E> c) Adds all of the elements in the specified collection to this set if they're not already present (optional operation) clear() Removes all of the elements from this set (optional operation) contains (0bject o) Returns true if this set contains the specified element. containsAll (Collection> c) Returns true if this set contains all of the elements of the specified collection. boolearn void boolearn boolearn equals (Object o) Compares the specified object with this set for equality hashCode () Returns the hash code value for this set. boolearn boolearn isEmpty() Returns true if this set contains no elements iterator() Returns an iterator over the elements in this set. Iterator
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help