Decision Trees and Hash Tables

Question 1 a) 2-4 Tree with 13 3-nodes



b) After 1 minimum insertion:




After 2 minimum insertions:





After 3 minimum insertions:





1
After 4 minimum insertions:



After 5 minimum insertions:



c) After 1 max deletion:



After 2 max deletions:




After 3 max deletions:




After 4 max deletions:




2
After 5 max deletions:




Question 2 a) DFS Traversal order: v5 → v4 → v2 → v4 → v3 → v1 → v10 → v9 → v8 → v6 → v7 Discovery Edges Back Edges (v5,v4) (v10,v3) (v4,v2) (v6,v3) (v4,v3) (v6,v5) (v3,v1) (v7,v8) (v1,v10) (v10,v9) (v9,v8) (v8,v6) (v6,v7)
b) BFS Traversal Levels:
Level Nodes Discovery Edges Cross Edges L1 v4 (v5,v4) v6 (v5,v6) L2 v2 (v4,v2) (v6,v3) v3 (v4,v3) v7 (v6,v7) v8 (v6,v8) L3 v1 (v3,v1) (v7,v8) v10 (v3,v10) v9 (v8,v9) L4 (v1,v10) (v10,v9)
3
Question 3 a) Dijkstra’s algorithm trace:
New Vertex S P U X Q Y V R W T New Edge S 0X 6 3* ∞ ∞ ∞ ∞ ∞ ∞ ∞ U 0X 6 3X 4* ∞ ∞ 6 ∞ ∞ ∞ (S,U) X 0X 6* 3X 4X 12 10 6 ∞ ∞ ∞ (U,X) P 0X 6X 3X 4X 11 10 6* ∞ ∞ ∞ (S,P) V 0X 6X 3X 4X 11 10* 6X ∞ 10 ∞ (U,V ) Y 0X 6X 3X 4X 11 10X 6X 11 10* ∞ (X,Y ) W 0X 6X 3X 4X 11* 10X 6X 11 10X 15 (V,W) Q 0X 6X 3X 4X 11X 10X 6X 11* 10X 15 (P,Q) R 0X 6X 3X 4X 11X 10X 6X 11X 10X 13* (Y,R) T 0X 6X 3X 4X 11X 10X 6X 11X 10X 13X (R,T)
Minimum Spanning Tree:
S
U P
X V Q
Y W
R
T
b) SUXYRT is the shortest path from S to T.
4
Question 4 a) Insertion into a hash table using linear probing with the function h(X) = X mod 11 on the following elements: 3, 32, 46, 58, 57, 26, 17, 74.
h(X) 0 1 2 3 4 5 6 7 8 9 10 x 46 3 58 57 26 17 74 32
b) Four elements would have to be probed before we find 57. This is because 57 mod 11 = 2 but 57 is found at the 5th position. c) Eight elements would have to be probed before we realize 68 is not in the table. This is because 68 mod 11 = 2 but the first empty element is found at the 9th position. d) i) Insertion into a hash table using linear probing with the double hash function h2(X) = 7−(X mod 7) on the following elements: 3, 32, 46, 58, 57, 26, 17, 74. h(X) 0 1 2 3 4 5 6 7 8 9 10 x 74 46 3 26 17 58 57 32 ii) Four elements would have to be probed before we find 57. This is because 57 mod 11 = 2 but element 46 is found at position 2. So then the double hashing algorithm is applied 7−(57 mod 7) = 6. Jumping 6 buckets we find 58, jumping 6 more we find 3, jumping 6 more we find 57. ∴ 57 is found on the 4th probe. iii) Six elements would have to be probed before we realize 68 is not in the table. This is because 68 mod 11 = 2 but element 46 is found at position 2. So then the double hashing algorithm is applied 7−(68 mod 7) = 2. Jumping 2 buckets we find 26, jumping 2 more we find 17, jumping 2 more we find 58, jumping 2 more we find 32 and finally jumping 2 more we find null. ∴ 68 is determine to not be in the hash table on the 6th probe.