Outline

in-class exercises

what is the probing sequence if the hash table size is 11, and h(key) = 4? answer for each of linear addressing, quadratic addressing, and double hashing where h₂(key) = 5
using h(key) = key mod table size and linear addressing, insert elements with key 56, 48, 40, 13 into a table of size 7
remove the element with key 48
locate the element with key 13
repeat these steps with a new hash table that uses chained hashing

four kinds of equality:
- == is true if and only if two references are to the exact same object (or for basic types)
- object1.equals(object2) is true if object1's equals method (in its wisdom) decides they are the same
- object1.compareTo(object2) is 0 if the compareTo method decides they are the same
- object1.compare(object2, object3) is similar
the equals method should be:
- symmetric: a.equals(a) should always be true
- reflexive: a.equals(b) == b.equal(a)
- transitive: if a.equals(b) and b.equals(c) iff a.equals(c)
- consistent: successive identical calls should return the same result
- if a is not null, a.equals(null) == false
the equals method can be overridden for any class.
if equals is not overridden, it defaults to ==

the mathematical function sgn returns -1 if its argument is negative, 1 if it is positive, and 0 if it is zero
in Java, two kinds of comparison:
- Comparable<T> interface, specifies the
  int compareTo(T x) method
- Comparator<T> interface, specifies the
  int compare(T x1, T x2) method (which could be static, but isn't)
both comparison methods should have the following properties
- symmetric: sgn(compare(a, b)) == - sgn(compare(b, a))
- transitive: if (((compare(a, b) > 0) && ((compare(b, c) > 0)), then ((compare(a, c) > 0)
- consistent: if (compare(a, b) == 0), then sgn(compare(a, c)) should be the same as sgn(compare(b, c))
when building ordered linked lists, heaps, or when sorting, can use either interface, e.g. class Collections has two different methods for sorting,
- static <T extends Comparable<? super T>> void sort(List<T> list)
- static <T> void sort(List<T> list, Comparator<? super T> c)
Comparable seems to be more common than Comparator

finding duplicate elements in a list
making a list of elements, where each element must occur at most once
preparing for future binary search (dictionary, phone book)
presenting data in an appropriate format, e.g. for printing (bank statement sorted by date)
comparing two lists to find out which elements are in one, the other, or both
merging multiple sorted collections into a new sorted collection, with or without duplicates

Java has
```
public static void sort(x[] items);
public static void sort(x[] items, int fromIntex, int toIndex);
```
for type x being any one of:
- int
- Object -- the objects must be Comparable
- Comparator, in which case the last argument is the comparator object
as mentioned above, there is also a sort method declared on lists of objects that are either Comparable, or can be compared by a Comparator.compare() method

start with an unsorted array a
the empty sub-array (elements 0 to -1) is sorted
to extend this sub-array, search in 0..a.length-1 for the smallest element at index i (i is at least 0 and at most a.length - 1)
swap the elements at index i and at index 0
now, the sub-array with elements 0..0 is sorted
to extend this sub-array, search in 1..a.length-1 for the smallest element at index i
swap the elements at index i and at index 1
now, the sub-array with elements 0..1 is sorted
in-class exercise (in groups of 2 or 3): write code to implement selection sort
in-class exercise: how long does selection sort take?

start with an unsorted array a
loop through all the elements of array a, swapping any that are not sorted
repeat until the array is sorted
in-class exercise: how long might this take? how long does it take in the best case? how do these compare to selection sort?
historical trivia: if the data is stored on a magnetic tape, how many passes of the tape are needed to sort the entire tape? (this is assuming the tape can store much more data than the memory of the computer)
current trivia: bubble sort can be done in parallel on n processors...

in selection sort, find the smallest element, and put it in the next position
in insertion sort, take the next element, and put it in the right place
trivia: card players typically use insertion sort to arrange their decks
the sub-array at the beginning of the array is already sorted, just as in selection sort
the next element e is always taken from the next index in the array
elements greater than e (in the sorted part of the array) are shifted up one position, to free the position where element e will be stored
in-class exercise (in groups of 2 or 3): write code to implement insertion sort
in-class exercise: how long does insertion sort take?