Description
Take-Home Assignment 2a – Join Strings • Use custom linked list implementation (TailedLinkedList.java suffices) • Use ArrayList (or a regular TailedLinkedList[] array) • When concatenating string b to a (ie. string is a + b), set tail node of a to point to head node of b • Update tail node pointer of a to tail node of b • No need to set b to null in the array after concatenation, as b is never referenced again (but you can do so if you want) • Use StringBuffer or StringBuilder when constructing the final answer Take-Home Assignment 2b – Teque • All operations need to run in O(1) time • For access to an element in O(1) time (get() operation), this suggests the use of an array • Pushing to the back can easily be done in O(1) time too • For adding to the front, instead of fixing index 0 as the front, allow for the front index to change • This can be accomplished by using a circular array, with head and tail indices, as well as size attribute Take-Home Assignment 2b – Teque • How to insert to middle? • Split into two circular arrays, one contains the front half (array 1), while the other contains the back half of the ADT (array 2) • Balance out the number of elements between the two arrays after every push operation if necessary, so the middle is easily accessible • Should never need to move more than 1 element between the two arrays, so this is still O(1) • For a get(n) operation using 2 arrays, access the nth element in array 1, or the (n-(size of array 1)th) element in array 2 if n exceeds the size of array 1 Lab 5 – Hashing • Two different forms of hash tables are provided by Java • HashMaps involve a key-value pair • The key is the object which is hashed, and then put into the HashMap depending on its resulting hash code • The value is a separate object that is associated with that key, and its contents are not considered when computing the hash code of the key • The entire key-value pair is called an entry • HashSets simply involve one object, that acts as both the key and the value Lab 5 – Hashing • Note: there is also a Hashtable class which behaves in the same manner as a HashMap, but is generally slower than HashMap for the purposes of CS2040 • The reason is similar to ArrayList vs Vector ie. synchronisation Lab 5 – HashSet Method name Description Time .add(YourClass element) Adds element to the HashSet O(1) .clear() Clears the HashSet O(n) .contains(Object o) Checks if o is in the HashSet, based off the object’s equals() method O(1) .isEmpty() Checks if the HashSet is empty O(1) .remove(Object o) Removes o if it is in the HashSet, based off the object’s equals() method O(1) .size() Returns the number of elements in the HashSet O(1) Lab 5 – HashMap • HashMaps are the first class encountered in this module that require the use of more than one generic • To declare a HashMap with an Integer as the key, and a String as the value: • HashMap<Integer, String> map = new HashMap<Integer, String>(); • The two generics used need not be different eg. to use an integer as the key, and another integer as the value: • HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); Lab 5 – HashMap • HashMaps are generally useful in answering queries where the key is known, but the value is unknown • Eg. if we want to know which stall at a food court sells a certain food item, we could store a key-value pair of all foods, where the key is the food item’s name, and the value is the stall name. • If we have a craving for a certain food item later, we use the food item’s name to look up the HashMap, and check the value (stall name) associated with that key • Effectively, using the key as a “reference” for the value Lab 5 – HashMap Method name Description Time .put(YourClass key, YourClass value) Adds key to the HashMap with the value value O(1) .clear() Clears the HashMap O(n) .containsKey(Object o) Checks if key o is in the HashMap, based off the object’s equals() method O(1) .containsValue(Object o) Checks if value o is in the HashMap, based off the object’s equals() method O(n) .get(Object o) Gets the value corresponding to the key o O(1) .isEmpty() Checks if the HashMap is empty O(1) .remove(Object o) Removes the entry with key o if it is in the HashMap, based off the object’s equals() method O(1) .size() Returns the number of elements in the HashMap O(1) Lab 5 – HashMap (cont.) Method name Description Time .entrySet() Returns a set of all entries in the HashMap O(1) .keySet() Returns a set of all keys in the HashMap O(1) .values() Returns a collection of all values in the HashMap O(1) Unlike HashSet, it is not possible to iterate through a HashMap (eg. enhanced for-loop) directly. You will need to use the above methods to access an iterable form of the data stored within One-Day Assignment 4 – Conformity • Given the course combinations of students, determine how many students are taking one of the most popular combination of courses • There can be multiple combinations of courses which are tied for the most popular combination eg: • (100, 101, 102, 103, 104) – 4 students • (101, 102, 103, 104, 105) – 2 students • (102, 103, 104, 105, 106) – 4 students • Your answer should be 4 + 4 = 8 (the students taking the first and third combinations) • Note that course combinations can be given in different orders, but should be considered as the same course combination • Eg (100, 101, 102, 103, 488) is the same combination as (103, 102, 101, 488, 100) as given in Sample Input 1