Worksheet: J3

Worksheets are self-guided activities that reinforce lectures. They are not graded for accuracy, only for completion. Worksheets are due by Sunday night before the next lecture.

• Github Classroom Link: https://classroom.github.com/a/ElLcz5hd

Questions

1. Consider the class declearation below:

   // Is this possible?
   public class Lion extends Mammal, Carnivor {
       // ...
   }
   

   • Explain why the following class declaration is not possible in Java.
   • What are the limitations of the extends key word?
   • How can you accomplish this inheritance structure task in Java?

   Reveal Solution

   Java classes can only extend from one class! So we can have Lion extends Mammal or Lion extends Carnivor, but not both. To accomplish functionality similar to this, we would have:

   public class Lion extends Mammal implements Carnivor {
       // ...
   }
   

   As it makes sense for an animal to inherit from the specific class it is (Mammalia), and for it to have an interface that represents how it interacts (or interfaces) with food.

2. What are some of the functional differences between an abstract class and an interface? Use the example below to answer this question.

   public abstract class Employee {
       // ...
   }
   
   // vs.
   
   public interface Employee {
       //...
   }
   

   Reveal Solution

   Abstract classes and interfaces can:

   • Provide just method declarations that a class must realize

   Abstract classes do (and interfaces do not):

   • Provide methods and constructors a child class can choose to use, or override
   • Provide inherited class variables
   • Have access modifiers for inherited methods
   • Require the child class to inherit only itself, and no other class

3. Suppose you have interfaces Adder and Multiplier:

   public interface Adder<T> {
       T add(T a, T b);
   }
   

   public interface Multiplier<T> {
       T multiply(T a, T b);
   }
   

   Finish the implementation of the IntegerCalculator and FloatCalculator classes below.

   public class IntegerCalculator implements Adder<Integer>, Multiplier<Integer> {
       private String calculatorName;
   
       public IntegerCalculator(String calculatorName) {
           this.calculatorName = calculatorName;
       }
   
       public String getCalculatorName() {
           return calculatorName;
       }
   
       // TODO: add the methods needed to implement the adder and multiplier interfaces.
   }
   

   public class FloatCalculator implements  Adder<Float>, Multiplier<Float>{
       private String calculatorName;
   
       public FloatCalculator(String calculatorName) {
           this.calculatorName = calculatorName;
       }
   
       public String getCalculatorName() {
           return calculatorName;
       }
   
       // TODO: add the methods needed to implement the adder and multiplier interfaces.
   }
   

   Reveal Solution

   public class IntegerCalculator implements Adder<Integer>, Multiplier<Integer> {
       // ...
   	public Integer add(Integer a, Integer b) {
   		return a + b;
   	}
   
   	public Integer multiply(Integer a, Integer b) {
   		return a * b;
   	}
   }
   

   public class FloatCalculator implements  Adder<Float>, Multiplier<Float>{
       // ...
   	public Float add(Float a, Float b) {
   		return a + b;
   	}
   
   	public Float multiply(Float a, Float b) {
   		return a * b;
   	}
   }
   

4. Read about the ArrayList class provided in the Java util package.

   • Provide a one paragraph description of an ArrayList implementation in Java.
   • Draw a UML diagram of ArrayList to Object.
   • What is ArrayList’s direct ancestor class?
   • What interfaces does ArrayList implement?
   • Choose one of the interfaces and explain what property of the class come from that interface.

   Reveal Solution

   • ArrayList is an array of some type, that implements the List interface, meaning it has methods so the user of ArrayList has precise control over where in the list each element is inserted. The user can access elements by their integer index (position in the list), and search for elements in the list. When the array reaches its total capacity, it is resized.
   • AbstractList
   • See first answer for an explanation of the List interface. Cloneable, means that there is some clone method that will return a complete copy in memory of the implementing class, and Serializable, provides a method that guarantees the class can be “serialized”, or turned into some ascii representation.

5. Read about the Hashtable class provided in the Java util package.:

   • Provide a one paragraph description of a Hashtable implementation in Java.
   • Draw a UML diagram of Hashtable to Object.
   • What interfaces does Hashtable implement?
   • Do any other classes in the Java util realize a Dictionary and a implement a Map?
   • Choose one of the interfaces and explain what property of the class come from that interface.

   Reveal Solution

   • Hashtable maps objects of one type to another, by calling hashCode on the key object, in order to find the value. This means that any type used for the key must implement that method. Similar to the hashmap in the boggle project, the Hashtable class has an array of buckets, and when getting a value, the key hash maps to one of these buckets, which is then searched.
   • Map, Cloneable, Serializable
   • No other class extends Dictionary, but many classes implement map, such as TreeMap and AbstractMap.
   • Map Provides methods so a user can pass some sort of key, and a value is returned. It also guarantees there is some list of keys, values, and key-value mappings available. Finally, it provides users the ability to check if the mapping is empty, if it contains a key or value, and a way to delete or update key-value pairs. See previous for Cloneable and Serializable

6. Read about the TreeMap class provided in the Java util package.

   • Provide a one paragraph description of a TreeMap implementation in Java.
   • Draw a UML diagram of TreeMap to Object.
   • What is TreeMaps’s direct ancestor class?
   • What interfaces does TreeMap implement?
   • Choose one of the interfaces and explain what property of the class come from that interface.

   Reveal Solution

   • Another map, except that instead of implementing it using a hash table, it is implemented using a Red-Black tree (see here) for a refresher). What happens, is we search for a node that represents our key-value pair.
   • AbstractMap, which is an abstract class implementing Map but with only some basic methods implemented
   • NavigableMap, Cloneable, Serializable
   • NavigableMap is similar to the Map interface, except it also requires that all keys and values can be sorted. The additional methods required are ways for the user to get either the max/min keys and values, or the key/value that is immediately greater/lesser than a given key or value. We see that since a Red-Black tree is a sorted binary tree, that means the data stored in it must be sorted, and so we implement NavigableMap.

7. Take a look at the documentation for LinkedHashSet: https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/LinkedHashSet.html
   and HashSet:
   https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/HashSet.html

   When would it be preferable to use a LinkedHashSet instead of a HashSet?

   Reveal Solution

   We would use the LinkedHashSet when we have a set of items that we want to keep in a specific unchanging order. For example, if we want a set of colors, we’d use HashSet, since there can only be at most one instance of a color (it wouldn’t make sense to store two identical reds), but there isn’t an order to colors (the rainbow is only one way to order them, but it’s not THE way to). If we wanted a set of integers, we’d want to use LinkedHashSet, since integers are inherently comparable and sortable, and we don’t want them to be in a random order.

8. Modify the code below to use Java generics. Your code should not need casting, remove the (String) casting before the .get method.

   import java.util.HashMap;
   
   public class TestHashMap {
   
       public static void main (String[] argv) {
           // Create a new hashmap.
           Hashtable fabFour = new HashMap();
   
           // Insert four key and value pairs.
           fabFour.put("John", "John Lennon");
           fabFour.put("Paul", "Paul McCartney");
           fabFour.put("George", "George Harrison");
           fabFour.put("Ringo", "Ringo Star");
   
           // Use a key to retrieve a value.
           String fullName = (String) fabFour.get("Ringo");
   
           // Prints "Ringo Star"
           System.out.println(fullName);
       }
   }
   

   Reveal Solution

   public class TestHashMap {
   
       public static void main(String[] argv) {
           // Create a new hashmap.
           HashMap<String,String> fabFour = new HashMap<String,String>();
   
           // Insert four key and value pairs.
           fabFour.put("John", "John Lennon");
           fabFour.put("Paul", "Paul McCartney");
           fabFour.put("George", "George Harrison");
           fabFour.put("Ringo", "Ringo Star");
   
           // Use a key to retrieve a value.
           String fullName = fabFour.get("Ringo");
   
           // Prints "Ringo Star"
           System.out.println(fullName);
       }
   }
   

9. Provide a 1-to-2 paragraph explanation for why we need Generics? You can use the sample code (above and below) to over this explanation.

   Reveal Solution

   A lot of what we do as computer scientists, is writing and using abstractions of
   different things. Methods and functions provide ways for us to perform some
   operation on some data of a specific type, such as integers, over and over
   again, such as adding two numbers. Data structures such as classes provide ways
   for us to give data some shape and functionality, if it can’t just be
   represented by a number (as most things can’t). What if we want to operate on
   some data, but we don’t care about the specific type of the data, such as
   putting it in a list. From here we see the point of generics, a way to operate
   on any “generic” data, or data with any type. Another way to think about
   generics in a more practical sense is that they are a way to store and work with data types,
   instead of actual data. An example may be comparing different types of movies, instead of different movies.

10. What is the output of this program? Please explain.

    public class TestHashMap {
    
        public static void main(String[] argv) {
            // Create a new hashtable.
            HashMap<String, Integer> carsTable = new HashMap<String, Integer>();
    
            // Insert key and value pairs
            carsTable.put("Lamborghini", 225);
            carsTable.put("Porsche", 202);
            carsTable.put("Jeep", 110);
            carsTable.put("Mustang", 144);
            carsTable.put("Jeep", 90);
    
            Integer topSpeedOfJeep = carsTable.get("Jeep");
            System.out.println(topSpeedOfJeep);
        }
    }
    

    Reveal Solution

    The output is 90, as we are getting the value associated with the key “Jeep”.

11. What is “Erasure” with java generics?

    For the code below, what does the code “erase” to?

     public static void main(final String args[]) {
            Shelf<String> favorite_words = shelfBuilder();
            favorite_words.addItem("Zoetrope");
            favorite_words.addItem("Succinct");
            //...        
            String s = favorite_words.getItem(1);
            System.out.println(s);
        }
    

    Reveal Solution

    The Java runtime actually doesn’t know anything about generics, when you compile
    a Java program with generics in them, at compilation time all “generic” types
    are replaced with what they should be. Essentially, when we use a generic, at
    compilation time the compiler essentially changes the Shelf class to only use the Object type, so wherever we see a T it’s replaced with Object. From there, every time we do something that should return as a specific type T, we replace with a cast to that specific type.

    We see this program then erases to:

     public static void main(final String args[]) {
            Shelf favorite_words = shelfBuilder();
            favorite_words.addItem((Object)"Zoetrope");
            favorite_words.addItem((Object)"Succinct");
            //...        
            String s = (String)favorite_words.getItem(1);
            System.out.println(s);
        }
    

12. Why is the following code invalid in Java? Use the erasure to show why it fails after the generic is erased.

    public class FooBarBaz<T>{
       T array[];
       public FooBarBaz{
          array = new T[];
       }
    }
    

    Reveal Solution

    The code erases to:

    public class FooBarBaz{
       Object array[];
       public FooBarBaz{
          array = new Object[];
       }
    }
    

    We see this code won’t work as the array doesn’t have a size.

13. Finish the main method in the TestShelf class above.

    Expected output:

    Shakespeare Characters: Hamlet Othello Cordelia Juliet
    Famous Integers: 13 23 42 1729
    

    import java.util.ArrayList;
    import java.util.List;
    
    public class Shelf<T> {
        private List<T> shelfItems;
    
        private String shelfName;
    
        public Shelf(String shelfName) {
            this.shelfName = shelfName;
            shelfItems = new ArrayList<T>();
        }
    
        public int addItem(T item) {
            shelfItems.add(item);
            return shelfItems.size();
        }
    
        public void printShelf() {
            System.out.print(shelfName + ": ");
            for(T item: shelfItems) {
                System.out.print(item.toString() + " ");
            }
            System.out.println();
        }
    }
    

    public class TestShelf {
        public static void main(final String args[]) {
    
            // TODO: Create a shelf to store Shakespeare character names:
            //       Hamlet, Othello, Cordelia, and Juliet
            // TODO: Then print the shelf.
    
    
            // TODO: Create a shelf to store famous integers:
            //       13, 23, 42, 1729,
            // TODO: Then print the shelf.
    
    
        }
    }
    

    Reveal Solution

        public static void main(String[] args){
            Shelf<String> shakespeare = new Shelf<>("Shakespeare Characters");
            shakespeare.addItem("Hamlet");
            shakespeare.addItem("Othello");
            shakespeare.addItem("Cordelia");
            shakespeare.addItem("Juliet");
            Shelf<Integer> integers = new Shelf<>("Famous Integers");
            integers.addItem(13);
            integers.addItem(23);
            integers.addItem(42);
            integers.addItem(1729);
            shakespeare.printShelf();
            integers.printShelf();
        }
    

14. Consider the following code snippets for a LinkedList you may implement and a main method:

    public class LinkedList{
       private class Node{
          int data;
          Node next;
       }
       Node head;
       void push(int data);
       int get(int idx);
       //...   
    

    public class TestingLinkedList{
      public class static main(String args[]){
         LinkedList ll = new LinkedList();
         
         for(int i=0;i<100000;i++){
             ll.push(i*3);
         }
         
         for(int i=0;i<100000;i++){
             System.out.println(""+ll.get(i)); //<-- MARK
         }
      }
    
    }
    
    

    Explain why the line with MARK is extremely inefficient? Use Big-O to explain.

    Reveal Solution

    A linked list has a search time of O(n), since you must iterate through the
    whole list to know if something is in it or not. Therefore, the for loop that
    contains the marked line will have a cost of O(n) every single call, and it
    will be called once for each item. This means the total runtime cost will be
    O(n^2), which is not good :(.

15. Continuing with the example above, explain why expanding LinkedList to implement Iteraable solves the inefficiency problem you described above.

    Reveal Solution

    Iterable will keep track of where we are in the linked list, essentially holding a pointer to the last item we were at. This means everytime we get the next item, it’ll just return next of the current location, and move the pointer forward to the next item. This results in a loop that is only O(n), as we only see every item at most once.

16. Finish the main method below to use the fibonacci iterator to print out the sequence: 1 2 3 5 8 13 21 ...

    import java.util.Iterator;
    
    class Fibonacci implements Iterable<Integer> {
        public static void main(final String args[]) {
            Fibonacci fibonacci = new Fibonacci(21);
    
            // TODO:  Use the fibonacci iterator to print out the sequence: 1 2 3 5 8 13 21
    
        }
    
        private int max;
    
        public Fibonacci(int max) {
            this.max = max;
        }
    
        public Iterator<Integer> iterator() {
            return new FibonacciIterator();
        }
    
        private class FibonacciIterator implements Iterator<Integer> {
            int current = 1;
            int previous = 0;
    
            @Override
            public boolean hasNext() {
                return current + previous <= max;
            }
    
            @Override
            public Integer next() {
                int tmp = current;
                current += previous;
                previous = tmp;
                return current;
            }
        }
    }
    

    Reveal Solution

    Iterators are so cool!

      public static void main(final String args[]) {
          Fibonacci fibonacci = new Fibonacci(21);
          for(int i : fibonacci){
              System.out.print(i+" ");
          }
      }
    

17. Explain why the Comparable interface is an interface rather than class?

    Reveal Solution

    The only thing we want for something to be comparable is a function that tells us if one of it is greater than the other. That means we just want the class to define one function and thats it. We could do this using an abstract class, but we wouldn’t use any of the other functionality an abstract class provides, and then the class couldn’t extend any other class either, so we’d be using something with more power than we need, and limiting our options in the future. So instead we just use an interface.

18. Add the compareTo method in the Car class above. So that the main method will print out:

    Name: Lamborghini Top Speed: 225
    Name: Porsche Top Speed: 202
    Name: Mustang Top Speed: 144
    Name: Jeep Top Speed: 110
    

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    public class Car implements Comparable<Car> {
        public static void main(String[] args) {
            List<Car> carsList = new ArrayList<>();
            carsList.add(new Car("Porsche", 202));
            carsList.add(new Car("Jeep", 110));
            carsList.add(new Car("Mustang", 144));
            carsList.add(new Car("Lamborghini", 225));
    
            Collections.sort(carsList);
            for(Car car : carsList) {
                System.out.println("Name: " + car.getName() + " Top Speed: " + car.getTopSpeed());
            }
        }
        private String name;
        private Integer topSpeed;
    
        public Car(String name, Integer topSpeed) {
            this.name = name;
            this.topSpeed = topSpeed;
        }
    
        public String getName() {
            return name;
        }
    
        public Integer getTopSpeed() {
            return topSpeed;
        }
    
        // TODO: Complete the Car class by adding the compareTo method
        //       needed to correctly implement Comparable<Car>.
    
    }
    
    

    Reveal Solution

    	public int compareTo(Car other) {
    		return this.topSpeed - other.topSpeed;
    	}
    

19. Find a natural hierarchy Object-Oriented relationship, such as the GWPerson, GWFaculty, GWStudent and GWStaff relationship. Develop an OOP design for these this natural hierarchy and label items as class, abstract classes, and interfaces. Provide a UML diagram and one paragraph describing the relationships.

    Reveal Solution

    We’ve given a few examples of these now, such as GWPerson, so you should be able to compare your own against these to check how you did.