Test 1 Answers
--------------
Problem 1 A

First loop is O(N), iterates N times, body is O(1)
Second loop iterates N/2 times so O(N) 

total N+N = O(N)
--
Problem 1 B
Inner loop iterates 0+1+2+...+n-1 times, total is
(n-1)n/2 = O(n^2)

Problem 1 C
loop increments p by 1 until p*p == n*n, this is a total of n
increments. so its O(n)

**********
PROBLEM 2

Collections.frequency is O(N) for an N-element list. Arrays.asList is
O(N) for an N-element list

total of inner loop is N+N+N+N = O(N)

Pat is right, Chris misses the inner loop and Leslie multiplies
instead of adding.

Part B

Find the largest value in the map. .values() returns a list/set of
values, .max finds the largest of these

Then iterate over all keys looking for a value == to max, this is a mode
(unique or not) return first found one.

Part C
for(String s : list) {
    if (! map.containsKey(s) map.put(s,0);
    map.put(s, map.get(s) + 1);
}

Part D
---
If list is NOT empty, the return in the loop will execute, but 
the Java compiler doesn't run code, it analyzes code. And the analysis
can't show that the loop will cause a return, so Java complains that the
function might not return a value, it must, 

**********
PROBLEM 3

Canonical returns a canonical string, so code creates an arraylist of
canonical strings, effectively mapping each string in parameter words to
a canonical equivalent. Nested loops look for all pairs of canonical
words, avoiding self/duplicate counts.

Part B .compareTo() for strings work, code is green

Part C:

if (map[ch] == 0) is .containsKey, array is auto-initialized to all
zeros.

map[ch] = current; is put, assigns value to key 'ch'

ret += map[ch] reads the value and increments ret, it's like .get
**********
PROBLEM 4

Go from 100,000 to one-million, multiply by 10. Linked code is linear
so 0.007 * 10 = 0.07

For arraylist, it's quadratic, multiply by 100
4.458 * 100 = 445 seconds

Part B ----- Linked: From 70 to 140 doubles, time is doubled. From fom
50 to 150 triple, time 0.003 to 0.010 about triple -- THEREFORE LINEAR

Array same timings: 2.129 to 8.401 * 4
1.063 to 9.654 about 9 times THEREFORE QUADRATIC

Part C
---
since while loop is linear in size of list, iter.add for LinkedList must
be O(1) to allow for O(N) code

Must be O(N) or O(k) for k-th add to get quadratic timing

Part D
--
If loop starts at 0, will copy 0 into 1 and 2, then 1 into 2/3 2 into
4/5, so first value copied everywhere, overwriting array.

list.set(k) is O(k) for linked and O(1) for array, this accounts for 
timings

**********
PROBLEM 5

Map is an interface, facilitates passing any kind of map to makeLabList,
not just Hash, not just Tree

ArrayLists can grow, arrays cannot. Easier to use arraylist since
size isn't known
--
for(String student: info.keySet()) {
    String[] labs = info.get(student);
    for(String lab : labs) {
        if (! rev.containsKey(lab)) {
            rev.put(lab,new ArrayList<String>());
        }
        rev.get(lab).add(student);
    }
}