Unit 9: Sets PDF

✎ Unit 9: Sets Unit Objectives. Here you will: consider how the ADT set can be used to solve a computing problem examine implementations of the set ADT in the JCF ✔...

✎ Unit 9: Sets Unit Objectives. Here you will: consider how the ADT set can be used to solve a computing problem examine implementations of the set ADT in the JCF ✔ SHS Wong DSA 9.Sets 1/23 ✎ Summary What is a set? How to implement a set data structure? I.e. how to model such a data structure and its standard operations? What is the typical time implication of performing an operation on a set collection? SHS Wong DSA 9.Sets 2/23 ✎ Summary What is a set? ➠         How to implement a set data structure? I.e. how to model such a data structure and its standard operations? What is the typical time implication of performing an operation on a set collection? When should we use a set collection? ✔ SHS Wong DSA 9.Sets 2/23 ✎ Summary What is a set? ➠         How to implement a set data structure? I.e. how to model such a data structure and its standard operations? e.g. array, linear linked structure,... What is the typical time implication of performing an operation on a set collection? When should we use a set collection? ✔ SHS Wong DSA 9.Sets 2/23 ✎ Summary What is a set? ➠         How to implement a set data structure? I.e. how to model such a data structure and its standard operations? e.g. array, linear linked structure,... What is the typical time implication of performing an operation on a set collection? O(n) When should we use a set collection? ✔ SHS Wong DSA 9.Sets 2/23 ✎ Set Operations Operation Purpose add Adds an element to the set. addAll Adds all elements in a given set to this set. remove Removes a specified element from the set. removeRandom Removes a random element from the set. union Performs set union between two sets. equals Checks if a given set is the same as this set. isSubset Checks if this set is a subset of a given set. contains Checks whether a specified element is on the set. isEmpty Checks whether the set is empty. size Returns the number of elements on the set. iterator Provides an iterator for this set retainAll removeAll isSubset ✔ intersection difference copy SHS Wong DSA 9.Sets 3/23 ✎ Exercise: implementing a pickRandom method In a set, the elements are unordered. When we pick an element from a set, we pick it at random. Let’s assume an array implementation of set. Write out an algorithm for returning a random element within a set collection. ✔ SHS Wong DSA 9.Sets 4/23 ✎ Exercise: implementing a pickRandom method In a set, the elements are unordered. When we pick an element from a set, we pick it at random. Let’s assume an array implementation of set. Write out an algorithm for returning a random element within a set collection. 1. Throws an appropriate exception when the set is empty. 2. Create a Random object. 3. Use an instance method of the Random object to generate a random integer between the range of 0 and n (where n is the size of the set). 4. The generated random number can then be used as an index for an element within the array that models our set for element retrieval. 5. Return the retrieved element. ✔ SHS Wong DSA 9.Sets 4/23 ✎ Exercise: Implementing pickRandom method Write out the implementation for returning a random element within a set collection. ✔ SHS Wong DSA 9.Sets 5/23 ✎ Exercise: Implementing pickRandom method Write out the implementation for returning a random element within a set collection. 1 public T pickRandom() throws EmptySetException { 2 if (isEmpty()) { 3 throw new EmptySetException(); 4 } 5 6 java.util.Random rand = new java.util.Random(); 7 8 int choice = rand.nextInt(count); 9 10 return contents[choice]; 11 } ✔ SHS Wong DSA 9.Sets 5/23 ✎ When should Set be used? One example of using set...... to model a game of bingo SHS Wong DSA 9.Sets 6/23 ✎ When should Set be used? One example of using set...... to model a game of bingo ✔ See also: A Bingo card generator web application at https://bingobaker.com/. SHS Wong DSA 9.Sets 6/23 ✎ Case Study: BINGO Each player has a bingo card with numeric values associated with the letters B-I-N-G-O. Letter/number combinations (printed on bingo balls) are picked at random, which the player marks on their card if possible. The first player to get five squares in a row on their bingo card wins. ✔ SHS Wong DSA 9.Sets 7/23 ✎ Case Study: Modelling a game of BINGO A bingo card... Which data entities in a BINGO application would be suitable for modelling by a set? ✔ SHS Wong DSA 9.Sets 8/23 ✎ Case Study: Modelling a game of BINGO A bingo card... Which data entities in a BINGO application would be suitable for modelling by a set? the collection of bingo balls a collection of bingo cards the collection of numbers on a bingo card ✔ SHS Wong DSA 9.Sets 8/23 ✎ Modelling a game of BINGO We assume that each player has been given a Bingo card, and would tick off the matching number on their Bingo card as the number of each randomly picked bingo ball announced by the host. We create an object of class BingoBall to represent one letter/number combination. The main program: 1. creates the balls, SHS Wong DSA 9.Sets 9/23 ✎ Modelling a game of BINGO We assume that each player has been given a Bingo card, and would tick off the matching number on their Bingo card as the number of each randomly picked bingo ball announced by the host. We create an object of class BingoBall to represent one letter/number combination. The main program: 1. creates the balls, 2. stores them in a set, SHS Wong DSA 9.Sets 9/23 ✎ Modelling a game of BINGO We assume that each player has been given a Bingo card, and would tick off the matching number on their Bingo card as the number of each randomly picked bingo ball announced by the host. We create an object of class BingoBall to represent one letter/number combination. The main program: 1. creates the balls, 2. stores them in a set, 3. draws one ball from the set and announce its number, and SHS Wong DSA 9.Sets 9/23 ✎ Modelling a game of BINGO We assume that each player has been given a Bingo card, and would tick off the matching number on their Bingo card as the number of each randomly picked bingo ball announced by the host. We create an object of class BingoBall to represent one letter/number combination. The main program: 1. creates the balls, 2. stores them in a set, 3. draws one ball from the set and announce its number, and 4. repeat Step 3 N − 1 times ✔ where N is the total number of balls required in each game. SHS Wong DSA 9.Sets 9/23 ✎ Bingo and BingoBall UML description of the Bingo and BingoBall classes ✔ SHS Wong DSA 9.Sets 10/23 ✎ Class BingoBall 1 public class BingoBall { 2 private char letter; 3 private int number; 4 5 8 public BingoBall (int num) { 9 number = num; 10 11 if (num