Algorithms and Programming Exam of 21 Febrauary 2020 Automatic Solution (with no graphical representation) ### Exercise 01 ### quick find 0 1 2 3 4 5 6 7 8 9 ------------------------------------ 0 1 2 3 4 5 6 7 8 9 7- 3 {nodes [7] go below node [3]} 0 1 2 3 4 5 6 3 8 9 3- 1 {nodes [3,7] go below node [1]} 0 1 2 1 4 5 6 1 8 9 5- 7 {nodes [5] go below node [1]} 0 1 2 1 4 1 6 1 8 9 1- 9 {nodes [1,3,5,7] go below node [9]} 0 9 2 9 4 9 6 9 8 9 0- 1 {nodes [0] go below node [9]} 9 9 2 9 4 9 6 9 8 9 6- 4 {nodes [6] go below node [4]} 9 9 2 9 4 9 4 9 8 9 1- 7 No change 9 9 2 9 4 9 4 9 8 9 8- 3 {nodes [8] go below node [9]} 9 9 2 9 4 9 4 9 9 9 3- 0 No change 9 9 2 9 4 9 4 9 9 9 4- 2 {nodes [4,6] go below node [2]} 9 9 2 9 2 9 2 9 9 9 9- 7 No change 9 9 2 9 2 9 2 9 9 9 2- 9 {nodes [2,4,6] go below node [9]} 9 9 9 9 9 9 9 9 9 9 ### Exercise 02 ### shell sort 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 V: 16 13 14 11 12 9 10 7 8 5 6 3 4 1 2 ------------------------------------------------ h = 13 ....................................... V: 1 13 14 11 12 9 10 7 8 5 6 3 4 16 2 V: 1 2 14 11 12 9 10 7 8 5 6 3 4 16 13 h = 4 ....................................... V: 1 2 14 11 12 9 10 7 8 5 6 3 4 16 13 V: 1 2 14 11 12 9 10 7 8 5 6 3 4 16 13 V: 1 2 10 11 12 9 14 7 8 5 6 3 4 16 13 V: 1 2 10 7 12 9 14 11 8 5 6 3 4 16 13 V: 1 2 10 7 8 9 14 11 12 5 6 3 4 16 13 V: 1 2 10 7 8 5 14 11 12 9 6 3 4 16 13 V: 1 2 6 7 8 5 10 11 12 9 14 3 4 16 13 V: 1 2 6 3 8 5 10 7 12 9 14 11 4 16 13 V: 1 2 6 3 4 5 10 7 8 9 14 11 12 16 13 V: 1 2 6 3 4 5 10 7 8 9 14 11 12 16 13 V: 1 2 6 3 4 5 10 7 8 9 13 11 12 16 14 h = 1 ....................................... V: 1 2 V: 1 2 6 V: 1 2 3 6 V: 1 2 3 4 6 V: 1 2 3 4 5 6 V: 1 2 3 4 5 6 10 V: 1 2 3 4 5 6 7 10 V: 1 2 3 4 5 6 7 8 10 V: 1 2 3 4 5 6 7 8 9 10 V: 1 2 3 4 5 6 7 8 9 10 13 V: 1 2 3 4 5 6 7 8 9 10 11 13 V: 1 2 3 4 5 6 7 8 9 10 11 12 13 V: 1 2 3 4 5 6 7 8 9 10 11 12 13 16 V: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 16 ### Exercise 03-10pt ### Expression evaluation Original expression: A * B - ( ( C + D - E ) * ( ( ( F - G ) * H ) / I ) ) Infix notation : A * B - C + D - E * F - G * H / I Prefix notation : - * A B * - + C D E / * - F G H I Postix notation : A B * C D + E - F G - H * I / * - ### Exercise 03-12pt ### IBST insert and search Insert intervals: [10-17] [ 4- 6] [ 3- 5] [ 9-13] [ 8-17] [12-15] [11-13] [16-20] [ 7- 9] [ 0- 3] [14-23] Breadth-first-order: Node [low,high] Max Left Right 1 10, 17 23 2 3 2 4, 6 17 4 5 3 12, 15 23 6 7 4 3, 5 5 8 NULL 5 9, 13 17 9 NULL 6 11, 13 13 NULL NULL 7 16, 20 23 10 NULL 8 0, 3 3 NULL NULL 9 8, 17 17 11 NULL 10 14, 23 23 NULL NULL 11 7, 9 9 NULL NULL Search interval: [19,21] Visiting [10,17]; No Intersection [19> 17] Right Recursion Visiting [12,15]; No Intersection [19> 13] Right Recursion Visiting [16,20]; Intersection Found Search interval: [ 1, 2] Visiting [10,17]; No Intersection [ 1<=17] Left Recursion Visiting [ 4, 6]; No Intersection [ 1<= 5] Left Recursion Visiting [ 3, 5]; No Intersection [ 1<= 3] Left Recursion Visiting [ 0, 3]; Intersection Found ### Exercise 04 ### hash-table Character keys Hash table size = 23 Number of keys = 13 Quadratic probing: c1=1.000000, c2=1.000000. Key: C A P T A I N M A R V E L Key=C k=003 Final=03 Key=A k=001 Final=01 Key=P k=016 Final=16 Key=T k=020 Final=20 Key=A k=001 Coll.= 1 Coll.= 3 Final=07 Key=I k=009 Final=09 Key=N k=014 Final=14 Key=M k=013 Final=13 Key=A k=001 Coll.= 1 Coll.= 3 Coll.= 7 Coll.=13 Final=21 Key=R k=018 Final=18 Key=V k=022 Final=22 Key=E k=005 Final=05 Key=L k=012 Final=12 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 - A - C - E - A - I - - L M N - P - R - T A V ### Exercise 05-10pt Directed matrix ... stated as such. UN-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 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 ### Graph visit BFS: Node=[ 0] A Discovery_time= 0 Predecessor=[-1] Node=[ 1] B Discovery_time= 1 Predecessor=[ 0] Node=[ 2] C Discovery_time= 1 Predecessor=[ 0] Node=[ 3] D Discovery_time= 2 Predecessor=[ 2] Node=[ 4] E Discovery_time= 2 Predecessor=[ 1] Node=[ 5] F Discovery_time= 2 Predecessor=[ 2] Node=[ 6] G Discovery_time= 3 Predecessor=[ 3] Node=[ 7] H Discovery_time= 3 Predecessor=[ 4] Node=[ 8] I Discovery_time= 5 Predecessor=[ 9] Node=[ 9] L Discovery_time= 4 Predecessor=[ 7] DFS: List of edges: [ 0] A -> [ 1] B : (T) Tree [ 1] B -> [ 4] E : (T) Tree [ 4] E -> [ 7] H : (T) Tree [ 7] H -> [ 9] L : (T) Tree [ 9] L -> [ 6] G : (T) Tree [ 6] G -> [ 7] H : (B) Back [ 9] L -> [ 8] I : (T) Tree [ 8] I -> [ 5] F : (T) Tree [ 5] F -> [ 3] D : (T) Tree [ 3] D -> [ 1] B : (B) Back [ 3] D -> [ 4] E : (B) Back [ 3] D -> [ 6] G : (C) Cross [ 5] F -> [ 6] G : (C) Cross [ 0] A -> [ 2] C : (T) Tree [ 2] C -> [ 3] D : (C) Cross [ 2] C -> [ 5] F : (C) Cross List of vertices: [ 0] A: dist_time= 1 endp_time=20 pred=[-1] - [ 1] B: dist_time= 2 endp_time=17 pred=[ 0] A [ 2] C: dist_time=18 endp_time=19 pred=[ 0] A [ 3] D: dist_time=10 endp_time=11 pred=[ 5] F [ 4] E: dist_time= 3 endp_time=16 pred=[ 1] B [ 5] F: dist_time= 9 endp_time=12 pred=[ 8] I [ 6] G: dist_time= 6 endp_time= 7 pred=[ 9] L [ 7] H: dist_time= 4 endp_time=15 pred=[ 4] E [ 8] I: dist_time= 8 endp_time=13 pred=[ 9] L [ 9] L: dist_time= 5 endp_time=14 pred=[ 7] H Reachable nodes from vertex [ 0] A: [ 0] A - [ 1] B - [ 2] C - [ 3] D - [ 4] E - [ 5] F - [ 6] G - [ 7] H - [ 8] I - [ 9] L - UN-reachable nodes from vertex [ 0] A: none ### Exercise 05-12pt 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 3 2 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 4 2 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 4 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 ### Graph DAG BFS (discovery and end-processing times): [ 0] A: dist_time= 1 endp_time=16 [ 1] B: dist_time= 2 endp_time= 5 [ 2] C: dist_time= 6 endp_time=15 [ 3] D: dist_time=17 endp_time=20 [ 4] E: dist_time= 3 endp_time= 4 [ 5] F: dist_time= 7 endp_time=14 [ 6] G: dist_time= 8 endp_time=13 [ 7] H: dist_time=18 endp_time=19 [ 8] I: dist_time=10 endp_time=11 [ 9] L: dist_time= 9 endp_time=12 Topological sort (inverse): [ 4] [ 1] [ 8] [ 9] [ 6] [ 5] [ 2] [ 0] [ 7] [ 3] E B I L G F C A H D Topological sort (direct): [ 3] [ 7] [ 0] [ 2] [ 5] [ 6] [ 9] [ 8] [ 1] [ 4] D H A C F G L I B E Shortest Paths: D H A C F G L I B E infy infy 0 2 5 6 9 7 3 4 Longest Paths: D H A C F G L I B E infy infy 0 2 5 6 9 13 3 4 ### Exercise 06 UN-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 Adjacency Matrix: 0 1 2 5 4 0 0 0 0 1 0 0 3 0 0 0 0 0 2 0 0 0 1 0 0 0 0 5 3 0 0 1 3 7 0 7 4 0 1 1 0 0 6 2 0 0 0 0 3 0 0 1 0 1 0 0 0 7 6 1 0 3 0 0 0 0 0 2 0 3 0 4 0 0 0 7 0 1 0 4 0 ### Graph MST (Kruskal and Prim) Kruskal Sorted array of edges: src dst weight: A B 1 C E 1 D E 1 F G 1 F I 1 A C 2 E H 2 B D 3 D F 3 G H 3 A E 4 H I 4 A D 5 E G 6 D G 7 D I 7 MST (list of edges): Edge [ 0] A - [ 0] B ==> weight = 1 Edge [ 2] C - [ 2] E ==> weight = 1 Edge [ 3] D - [ 3] E ==> weight = 1 Edge [ 5] F - [ 5] G ==> weight = 1 Edge [ 5] F - [ 5] I ==> weight = 1 Edge [ 0] A - [ 0] C ==> weight = 2 Edge [ 4] E - [ 4] H ==> weight = 2 Edge [ 3] D - [ 3] F ==> weight = 3 Total tree weight = 12 Prim MST (list of edges): Edge [ 0] A - [ 1] B ==> weight = 1 Edge [ 0] A - [ 2] C ==> weight = 2 Edge [ 2] C - [ 4] E ==> weight = 1 Edge [ 4] E - [ 3] D ==> weight = 1 Edge [ 4] E - [ 7] H ==> weight = 2 Edge [ 3] D - [ 5] F ==> weight = 3 Edge [ 5] F - [ 6] G ==> weight = 1 Edge [ 5] F - [ 8] I ==> weight = 1 Total tree weight = 12 util_free_all freeing up to 80 pointers. util_free_all freed exactly 0 pointers.