Algorithms and Programming Exam of 28 January 2020 Automatic Solution (with no graphical representation) Exercise 1 ### counting sort C : 0 1 2 3 4 5 6 7 8 9 10 11 -- A: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ------------------------------------------------------------------------------------------ -- A: 6 3 2 4 10 9 3 0 11 3 4 9 7 10 2 C1: 0 0 0 0 0 0 0 0 0 0 0 0 C2: 1 0 2 3 2 0 1 1 0 2 2 1 C3: 1 1 3 6 8 8 9 10 10 12 14 15 C3: 1 1 2 6 8 8 9 10 10 12 14 15 -- B: 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 C3: 1 1 2 6 8 8 9 10 10 12 13 15 -- B: 0 0 2 0 0 0 0 0 0 0 0 0 0 10 0 C3: 1 1 2 6 8 8 9 9 10 12 13 15 -- B: 0 0 2 0 0 0 0 0 0 7 0 0 0 10 0 C3: 1 1 2 6 8 8 9 9 10 11 13 15 -- B: 0 0 2 0 0 0 0 0 0 7 0 9 0 10 0 C3: 1 1 2 6 7 8 9 9 10 11 13 15 -- B: 0 0 2 0 0 0 0 4 0 7 0 9 0 10 0 C3: 1 1 2 5 7 8 9 9 10 11 13 15 -- B: 0 0 2 0 0 3 0 4 0 7 0 9 0 10 0 C3: 1 1 2 5 7 8 9 9 10 11 13 14 -- B: 0 0 2 0 0 3 0 4 0 7 0 9 0 10 11 C3: 0 1 2 5 7 8 9 9 10 11 13 14 -- B: 0 0 2 0 0 3 0 4 0 7 0 9 0 10 11 C3: 0 1 2 4 7 8 9 9 10 11 13 14 -- B: 0 0 2 0 3 3 0 4 0 7 0 9 0 10 11 C3: 0 1 2 4 7 8 9 9 10 10 13 14 -- B: 0 0 2 0 3 3 0 4 0 7 9 9 0 10 11 C3: 0 1 2 4 7 8 9 9 10 10 12 14 -- B: 0 0 2 0 3 3 0 4 0 7 9 9 10 10 11 C3: 0 1 2 4 6 8 9 9 10 10 12 14 -- B: 0 0 2 0 3 3 4 4 0 7 9 9 10 10 11 C3: 0 1 1 4 6 8 9 9 10 10 12 14 -- B: 0 2 2 0 3 3 4 4 0 7 9 9 10 10 11 C3: 0 1 1 3 6 8 9 9 10 10 12 14 -- B: 0 2 2 3 3 3 4 4 0 7 9 9 10 10 11 C3: 0 1 1 3 6 8 8 9 10 10 12 14 -- B: 0 2 2 3 3 3 4 4 6 7 9 9 10 10 11 -- A: 0 2 2 3 3 3 4 4 6 7 9 9 10 10 11 Exercise 3-10pt ### Tree read and visit Breadth-order: Node Key Left Right 1 12 2 3 2 9 4 5 3 7 NULL 6 4 13 NULL NULL 5 11 7 NULL 6 3 8 9 7 2 10 11 8 5 12 NULL 9 4 13 NULL 10 1 NULL NULL 11 6 NULL NULL 12 15 NULL NULL 13 10 NULL NULL Pre-order: 12 9 13 11 2 1 6 7 3 5 15 4 10 Pre-order: 13 9 1 2 6 11 12 7 15 5 3 10 4 Pre-order: 13 1 6 2 11 9 15 5 10 4 3 7 12 Exercise 3-12pt ### BST insert/extract root Insert keys: 7 29 13 18 23 15 17 Breadth-first-order: Node Key Left Right 1 7 NULL NULL Breadth-first-order: Node Key Left Right 1 29 2 NULL 2 7 NULL NULL Breadth-first-order: Node Key Left Right 1 13 2 3 2 7 NULL NULL 3 29 NULL NULL Breadth-first-order: Node Key Left Right 1 18 2 3 2 13 4 NULL 3 29 NULL NULL 4 7 NULL NULL Breadth-first-order: Node Key Left Right 1 23 2 3 2 18 4 NULL 3 29 NULL NULL 4 13 5 NULL 5 7 NULL NULL Breadth-first-order: Node Key Left Right 1 15 2 3 2 13 4 NULL 3 23 5 6 4 7 NULL NULL 5 18 NULL NULL 6 29 NULL NULL Breadth-first-order: Node Key Left Right 1 17 2 3 2 15 4 NULL 3 23 5 6 4 13 7 NULL 5 18 NULL NULL 6 29 NULL NULL 7 7 NULL NULL Breadth-first-order: Node Key Left Right 1 17 2 3 2 15 4 NULL 3 23 5 6 4 13 7 NULL 5 18 NULL NULL 6 29 NULL NULL 7 7 NULL NULL Extract key: 15 (position= 5) Node Key Left Right 1 17 2 3 2 13 4 NULL 3 23 5 6 4 7 NULL NULL 5 18 NULL NULL 6 29 NULL NULL Extract key: 18 (position= 3) Node Key Left Right 1 17 2 3 2 13 4 NULL 3 23 NULL 5 4 7 NULL NULL 5 29 NULL NULL Pre-order: 17 13 7 23 29 In-order: 7 13 17 23 29 Post-order: 7 13 29 23 17 Exercise 4 ### hash-table Character keys Hash table size = 23 Number of keys = 11 Double hashing. Key: F A R F R O M H O M E Key=F k=006 Final=06 Key=A k=001 Final=01 Key=R k=018 Final=18 Key=F k=006 Coll.= 6 Final=13 Key=R k=018 Coll.=18 Final=14 Key=O k=015 Final=15 Key=M k=013 Coll.=13 Final=04 Key=H k=008 Final=08 Key=O k=015 Coll.=15 Coll.= 8 Coll.= 1 Final=17 Key=M k=013 Coll.=13 Coll.= 4 Coll.=18 Final=09 Key=E k=005 Final=05 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 - A - - M E F - H M - - - F R O - O R - - - - Exercise 5 ### Heap insertion and extraction Min-Heap. Insert keys: 3 12 17 15 9 3 10 9 7 -1 -1 -1 Insert 3: 3 Insert 12: 3 12 Insert 17: 3 12 17 Insert 15: 3 12 17 15 Insert 9: 3 9 17 15 12 Insert 3: 3 9 3 15 12 17 Insert 10: 3 9 3 15 12 17 10 Insert 9: 3 9 3 9 12 17 10 15 Insert 7: 3 7 3 9 12 17 10 15 9 Extract 3: 3 7 9 9 12 17 10 15 Extract 3: 7 9 9 15 12 17 10 Extract 7: 9 10 9 15 12 17 Exercise 6 Directed matrix ... stated as such. Weighted matrix ... stated as such. Vertex list: [ 0] A [ 1] B [ 2] C [ 3] D [ 4] E [ 5] F [ 6] G [ 7] H [ 8] I [ 9] L Adjacency Matrix: 0 0 2 0 0 0 0 0 0 0 2 0 0 0 0 0 4 0 0 0 0 0 0 5 3 0 0 0 0 0 0 3 0 0 0 5 0 0 0 0 0 0 0 1 0 0 0 2 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 1 3 0 0 0 0 0 0 0 0 0 0 0 1 0 ### Graph SSSP (Dijkstra and Bellman-Ford) Dijkstra Shortest paths from vertex [ 0] A Node [ 0] A: 0 (pred=-1) Node [ 2] C: 2 (pred= 0) Node [ 4] E: 5 (pred= 2) Node [ 3] D: 6 (pred= 4) Node [ 7] H: 7 (pred= 4) Node [ 8] I: 8 (pred= 7) Node [ 1] B: 9 (pred= 3) Node [ 5] F: 9 (pred= 8) Node [ 9] L: 9 (pred= 7) Node [ 6] G: 11 (pred= 8) Bellman Ford Shortest paths from vertex [ 0] A Node [ 0] A: 0 (pred=-1) Node [ 1] B: 9 (pred= 3) Node [ 2] C: 2 (pred= 0) Node [ 3] D: 6 (pred= 4) Node [ 4] E: 5 (pred= 2) Node [ 5] F: 9 (pred= 8) Node [ 6] G: 11 (pred= 8) Node [ 7] H: 7 (pred= 4) Node [ 8] I: 8 (pred= 7) Node [ 9] L: 9 (pred= 7) util_free_all freeing up to 61 pointers. util_free_all freed exactly 0 pointers.