Week 12 - Introduction to Programming

Week 12 (Reading | Slides | Exercises)

Exercise 12.01: Explain, in your own words, the concept of polymorphism.

Exercise 12.02: Relate, in your own words, the concepts of inheritance (subtype polymorphism) to the concept of generics (parametric polymorphism).

Hint: When would you use inheritance over generics and vice versa?

Exercise 12.03: Write a generic method select with a type parameter T that takes two arguments x and y of type T and a boolean b, and returns x if b is true and y otherwise.

Exercise 12.04: Write a generic method extract with a type parameter T that takes an argument of type T[] and an argument of type T. The method returns the first element of the array, if it is non-empty. Otherwise, it returns the second argument.

Exercise 12.05: Write a generic method copy with a type parameter T that takes two arguments of type T[] and copies the content of one array to the other array.

Exercise 12.06: Write a generic method shuffle with a type parameter T that takes an argument of type T[]. Permute the array using the following algorithm: Repeatedly generate two random numbers i and j, where i and j must be a valid array indices and then swap the entry i with the entry j. Perform this operation n times where n is the length of the array.

Exercise 12.07 (Mandatory): Write a class Pair with two type parameters A and B to represent an immutable pair of values (i.e. the class should have two final fields of type A and B).

Add an appropriate constructor and getter methods.
- Do not add any setters, as the class should be immutable.
Add a method swap to the Pair class. The swap method should return a new pair where the first component becomes the second component and vice versa. For example, for the pair (true, 42) the method should return (42, true).
Add methods withFst and withSnd to the Pair class. Each method should take a type parameter C and return a new pair where the appropriate component has been updated. For example, calling withFst with the integer 42 on the pair (true, "Hello World") should return (42, "Hello World").

Exercise 12.08 (Mandatory): Write a class Dict that takes two type parameters K and V to represent a dictionary, i.e. a mapping from items of type K to items of type V. Internally, the dictionary should maintain a single array of pairs of type Pair<K, V>. Add the following methods:

V get(K key) returns the value associated with the given key, or null if the key is not found.
void put(K key, V value) updates the dictionary with a mapping from the key to the value. If the key already exists, its value is updated. Otherwise, a new pair is added.

You may assume the Dict can contain at most 100 entries.

Exercise 12.09: Explain, in your own words, the concept of an iterator.

Exercise 12.10: Explain, in your own words, the difference between the Iterator<T> and Iterable<T> interfaces.

Exercise 12.11: Write a program that constructs a list with each of the words: cuiusvis, hominis, est, errare, nullius, nisi, insipientis, in, errore, perseverare. Sort the list of words lexicographically and print the result to the terminal.

Exercise 12.12: Write a class Concatenate with a type parameter T that implements the Iterator<T> interface. The class should take two iterators in its constructor and behave as an iterator that returns elements from the first iterator until it is empty, and then returns elements from the second iterator.

Exercise 12.13: Explain, in your own words, the interfaces Comparable<T> and Comparator<T>.

Exercise 12.14: Write a Person class. A person has a first name, last name, and an age. Implement the Comparable<T> interface for the Person class. Persons should be ordered by first name, then last name, and finally by age. Construct a list of persons and sort it. Print the resulting list.

Exercise 12.15: Create a comparator (a class that implements Comparator<T>) for the Person class. The comparator should order persons by age, then by last name, and finally by first name. Construct a list of persons and sort it. Print the resulting list.

Exercise 12.16 (Mandatory): Write a class, which takes one type parameter E, to represent a multiset. A multiset is a set that counts how many times it contains each of its elements. Add the following methods:

int count(E e) returns the number of times the element e occurs in the multiset.
void add(E e) adds the element e to the multiset. (Adding increments its count.)
void remove(E e) removes the element e from the multiset. (Removing decrements its count.)
int size() returns the number of different elements in the set (non-duplicate count).

An element can never occur a negative number of times in a multiset.

Hint: Use an internal map of type Map<E, Integer>.

Exercise 12.17: Write a class, which takes two type parameters K and V, to represent a multimap. A multimap is a map from keys to sets of values. Add the following methods:

Set<V> get(K k) returns the set of values that k is mapped to, or the empty set if none.
void put(K k, V v) adds the value v to the set of values k is mapped to.
Set<V> values() returns the set of all values in the multimap.

Hint: Use an internal map of type Map<K, Set<V>>.

Exercise 12.18: Write a class, which takes two type parameters A and B, to represent a bidirectional map. A bidirectional map is a one-to-one correspondence between two sets. Add the following methods:

B getForward(A a) returns the element that a is mapped to.
A getBackward(B b) returns the element that b is mapped to.
void put(A a, B b) creates a mapping between a and b (and vice versa). If any mappings already exist for a or b, they are removed.

Hint: Use two internal maps of type Map<A, B> and Map<B, A>.