** Hashing ** (1) After set.add(15), set.add(5), set.add(13) value +------------+ 0 | 15 | +------------+ 1 | 5 | +------------+ 2 | | +------------+ 3 | 13 | +------------+ 4 | | +------------+ At the start of set.add(24) load factor = 0.6, so must rehash then add 24. For rehashing choose tablesize = 11 as it is the first prime that is twice as large as 5. Table after set.add(24): value +------------+ 0 | | +------------+ 1 | | +------------+ 2 | 13 | +------------+ 3 | 24 | +------------+ 4 | 15 | +------------+ 5 | 5 | +------------+ 6 | | +------------+ 7 | | +------------+ 8 | | +------------+ 9 | | +------------+ 10 | | +------------+ Final table after rehash, set.add(32), set.remove(13), set.add(17), set.add(44), set.remove(15), set.add(47) value +------------+ 0 | 44 | +------------+ 1 | | +------------+ 2 | R | +------------+ 3 | 24 | +------------+ 4 | 47 | +------------+ 5 | 5 | +------------+ 6 | 17 | +------------+ 7 | | +------------+ 8 | | +------------+ 9 | | +------------+ 10 | 32 | +------------+ (2) a. Final table: value +------------+ 0 | 29 | +------------+ 1 | 18 | +------------+ 2 | | +------------+ 3 | | +------------+ 4 | 70 | +------------+ 5 | 82 | +------------+ 6 | 50 | +------------+ 7 | 39 | +------------+ 8 | 15 | +------------+ 9 | | +------------+ 10 | | +------------+ b. 7 c. 11 d. 7/11 ~= .64 e. A search for 40 would cause the following buckets to be examined before the value would be declared to be not in the set: - bucket 7 (i.e. 40 % 11) - bucket 8 (i.e. 41 % 11) - bucket 0 (i.e. 44 % 11) - bucket 5 (i.e. 49 % 11) - bucket 1 (i.e. 56 % 11) - bucket 10 (i.e. 65 % 11) f. Yes. There is no guarantee for quadratic probing to work when the table size is prime and the table is more than half full. (3) public int hashCode() { return 3600 * hours + 60 * minutes + seconds; } ** Graphs ** (4) a. (draw it) b. directed c. cyclic d. weighted e. in degree: 3 out degree: 4 f. Path = V1 --> V3 --> V2 --> V5 --> V6 --> V4 g. list := {V0} list := {V1, V3} list := {V3, V4} list := {V4, V2, V5, V6} list := {V2, V5, V6} Path = V0 --> V1 --> v4 h. V0 V1 V2 V3 V4 V5 V6 0 inf/null inf/null inf/null inf/null inf/null inf/null list := {V0, V1, V2, V3, V4, V5, V6} V0 V1 V2 V3 V4 V5 V6 0 2/V0 inf/null 1/V0 inf/null inf/null inf/null list := {V1, V2, V3, V4, V5, V6} V0 V1 V2 V3 V4 V5 V6 0 2/V0 3/V3 1/V0 9/V3 2/V3 5/V3 list := {V1, V2, V4, V5, V6} V0 V1 V2 V3 V4 V5 V6 0 2/V0 3/V3 1/V0 9/V3 2/V3 5/V3 list := {V2, V4, V5, V6} V0 V1 V2 V3 V4 V5 V6 0 2/V0 3/V3 1/V0 9/V3 2/V3 3/V5 list := {V2, V4, V6} V0 V1 V2 V3 V4 V5 V6 0 2/V0 3/V3 1/V0 9/V3 2/V3 3/V5 list := {V4, V6} V0 V1 V2 V3 V4 V5 V6 0 2/V0 3/V3 1/V0 5/V6 2/V3 3/V5 list := {V4} V0 V1 V2 V3 V4 V5 V6 0 2/V0 3/V3 1/V0 5/V6 2/V3 3/V5 list := {} Path = V0 --> V3 --> V5 --> V6 --> V4 (5) a. A D B E G H F C b. AD BE AB DG EH FH CF (6) public int numStalkers(V stalked) { int numStalkers = 0; for (V v : this.vertices()) { if (!v.equals(stalked) && adjacencyMap.get(v).containsKey(stalked) && !adjacencyMap.get(stalked).containsKey(v)) { numStalkers++; } } return numStalkers; } Runtime: O(V) ** Disjoint Sets ** (7) a. 0 5 10 13 / / / / | \ \ \ \ | | | | | | | | | | 8 11 6 7 9 3 14 12 1 4 | 2 b. +------------+ 0 | -11 | +------------+ 1 | 0 | +------------+ 2 | 11 | +------------+ 3 | 0 | +------------+ 4 | 0 | +------------+ 5 | -2 | +------------+ 6 | 0 | +------------+ 7 | 0 | +------------+ 8 | 5 | +------------+ 9 | 0 | +------------+ 10 | -1 | +------------+ 11 | 0 | +------------+ 12 | 0 | +------------+ 13 | -1 | +------------+ 14 | 0 | +------------+ c. 0 5 10 13 / / / / / | \ \ \ \ | | | | | | | | | | | 8 2 11 6 7 9 3 14 12 1 4 (8) public void changeRep(int[] disjointSet, int x) { int oldRep = find(disjointSet, x); if (oldRep == x) { return; } int temp = disjointSet[oldRep]; for (int i = 0; i < disjointSet.length; i++) { if (disjointSet[i] == oldRep) { disjointSet[i] = x; } } disjointSet[oldRep] = x; disjointSet[x] = temp; } ** B Trees ** (9) M = 52 L = 8 (10) 2 2 3 --------- | 9 | | --------- 2 9 3 --------- | 4 | 9 | --------- 2 4 9 3 --------- | 4 | 9 | --------- 2 4 9 3 6 --------- | 4 | | --------- --------- --------- | 3 | | | 9 | | --------- --------- 1 3 4 9 2 6 --------- | 4 | | --------- --------- --------- | 3 | | | 7 | 9 | --------- --------- 1 3 4 7 9 2 6 --------- | 4 | | --------- --------- --------- | 3 | | | 7 | 9 | --------- --------- 1 3 4 7 9 2 6 8