Possible solution: Part A: Binary search trees and their traversal (8pt) --------------------------------------------- S = 613, 349, 930, 574, 192, 688, 154, 398, 628, 519, 225, 527, 292, 928, 147 A.1 (2pt): 613 349 192 154 147 / / / 225 / 292 / / 574 398 / 519 / 527 / / / 930 688 628 / / 928 / / / A.2 (2pt): 147 154 292 225 192 527 519 398 574 349 628 928 688 930 613 A.3 (2pt): You can choose to replace the root with the in-order successor value, or the in-order predecessor value: Eliminate root and replace by in-order successor: 628 349 192 154 147 / / / 225 / 292 / / 574 398 / 519 / 527 / / / 930 688 / 928 / / / Eliminate root and replace by in-order predecessor: 574 349 192 154 147 / / / 225 / 292 / / 398 / 519 / 527 / / 930 688 628 / / 928 / / / A.4 (2pt): S' = 519 225 628 154 349 574 928 147 192 292 398 527 613 688 930 Hashing and conflict resolution (6 pts) --------------------------------------- hashSeq: 613, 349, 930, 574, 192, 688, 154, 628, 527, 292, 928, 147 table initial i 3i i*i [0] _ _ 928 _ [1] _ _ _ _ [2] _ _ _ _ [3] _ _ _ _ [4] _ _ _ 928 [5] _ _ _ _ [6] _ _ _ _ [7] _ 527 527 527 [8] _ 688 688 688 [9] _ 349 349 349 [10] _ 930 930 930 [11] _ 628 628 147 [12] _ 192 192 192 [13] _ 613 613 613 [14] _ 574 574 574 [15] _ 154 292 154 [16] _ 292 147 292 [17] _ 928 154 628 [18] _ 147 _ _ [19] _ _ _ _ A.5 (2pt): table[17] = 928 A.6 (2pt): table[17] = 154 A.7 (2pt): table[17] = 628 Sorting (8pts) -------------- int arr[7] = {613,349,930,574,192,688,154}; A.8 (4pt): initial: 613,349,930,574,192,688,154 round 1: 930,192,613,574,154,688,349 round 2: 613,930,349,154,574,688,192 round 3: 154,192,349,574,613,688,930 A.9 Quicksort from chapter 11.11 in OpenDSA reads: void quicksort(Comparable* A[], int i, int j) { int pivotindex = findpivot(i, j); swap(A, pivotindex, j); // Stick pivot at end // k will be the first position in the right subarray int k = partition(A, i, j-1,A[j]); swap(A, k, j); // Put pivot in place if ((k-i) > 1) quicksort(A, i, k-1); // Sort left partition if ((j-k) > 1) quicksort(A, k+1, j); // Sort right partition } Observe the recursive calls (except for the first one), and hence a call to finpivot, are only made if the list has at least two elements. A.9.a a largest number of calls to quicksort corresponds to the worst case time complexity of the algorithm: It is for instance obtained for a monotonic sequence of pivots. For example: Call to quicksort pivot resulting call(s): quicksort([613,349,930,574,192,688,154],0,6) 154 quicksort([154,349,930,574,192,688,613],1,6) (only one recursive call) quicksort([154,613,349,930,574,192,688],1,6) 192 quicksort([154,192,930,574,688,613,349],2,6) (only one recursive call) quicksort([154,192,930,574,688,613,349],2,6) 349 quicksort([154,192,349,574,688,613,930],3,6) (only one recursive call) quicksort([154,192,349,574,688,613,930],3,6) 574 quicksort([154,192,349,574,688,613,930],4,6) (only one recursive call) quicksort([154,192,349,574,688,613,930],3,6) 613 quicksort([154,192,349,574,613,688,930],5,6) (only one recursive call) quicksort([154,192,349,574,613,688,930],5,6) 688 no more recursive calls! The idea is to choose the pivots so that the number of remaining elements are all to the left or to the right of the pivot. There will be as many calls as the number of elements in the array |arr| minus 1: each call chooses a pivot at the extremity until only one element remeains. This gives 6 calls to quicksort for this array with 7 elements. A.9.b a smallest number of calls to quicksort corresponds to the best case time complexity of the algorithm: It is obtained for a sequence of pivots that "cuts the sequences in halves". For example: Call to quicksort pivot resulting call(s): quicksort([613,349,930,574,192,688,154],0,6) 574 quicksort([154,349,192,574,688,613,930],0,2) then quicksort([154,349,192,574,688,613,930],4,6) quicksort([154,349,192,574,688,613,930],0,2) 192 no more calls (left and right sequences of size 1) quicksort([154,349,192,574,688,613,930],4,6) 688 no more calls (left and right sequences of size 1) The idea is to choose the pivots so that the number of remaining elements are "equally distributed" to the left and to the right of the pivot. This gives 3 calls to quicksort for this array with 7 elements. Graphs and shortest paths (8pts) -------------------------------- A.10 (2pt): DFS where edges of a given node are visited in increasing distance order: Linkoping - Norrkoping - Akersund - Motala - Jonkoping - Karlsborg - Alingsas - Goteborg A.11 (2pt): BFS where edges of a given node are visited in increasing distance order: Linkoping (queue: Norrkoping, Motala, Jonkoping) Norrkoping (queue: Motala, Jonkoping, Akersund) Motala (queue: Jonkoping, Akersund) Jonkoping (queue: Akersund, Karlsborg, Alingsas, Goteborg) Akersund (queue: Karlsborg, Alingsas, Goteborg) Karlsborg (queue: Alingsas, Goteborg) Alingsas (queue: Goteborg) Goteborg So the sequence of cities visited in BFS is: Linkoping - Norrkoping - Motala - Jonkoping - Akersund - Karlsborg - Alingsas - Goteborg A.12 (4pt) Dijkstra from Linkoping: (prio: Linkoping(0)) -> (prio: Norrkoping(43,LKP),Motala(55,LKP),Jonkoping(128,LKP)) * a shortest path from Linkoping to Norrkoping(43,LKP) uses Linkoping-Norrkoping (prio: Norrkoping(43,LKP),Motala(55,LKP),Jonkoping(128,LKP)) ->(prio: Motala(55,LKP),Jonkoping(128,LKP),Akersund(102+43=145,NOR)) * a shortest path from Linkoping to Motala(55,LKP) uses Linkoping-Motala (prio: Motala(55,LKP),Jonkoping(128,LKP),Akersund(145,NOR)) ->(prio: Akersund(145>55+48,MOT),Jonkoping(128<55+120,LKP)) * a shortest path from Linkoping to Akersund(103) uses Motala-Akersund (prio: Akersund(103,MOT),Jonkoping(128,LKP)) ->(prio: Jonkoping(128,LKP),Karlsborg(103+66=169,AKE),Alingsas(103+216=319,AKE)) * a shortest path from Linkoping to Jonkoping(128,LKP) uses Linkoping-Jonkoping (prio: Jonkoping(128,LKP),Karlsborg(169,AKE),Alingsas(319,AKE)) ->(prio: Karlsborg(169<128+99,AKE),Alingsas(319>128+125,JON),Goteborg(128+148=276,JON)) * a shortest path from Linkoping to Karlsborg (169,AKE) uses Akersund-Karlsborg (prio: Karlsborg(169,AKE),Alingsas(253,JON),Goteborg(276,JON)) ->(prio: Alingsas(253<169+155,JON),Goteborg(276,JON)) * a shortest path from Linkoping to Alingsas(253,JON) uses Jonkoping-Alingsas (prio: Alingsas(253,JON),Goteborg(276,JON)) ->(prio: Goteborg(276<253+47,JON)) * a shortest path from Linkoping to Goteborg(276,JON) uses Jonkoping-Goteborg Therefore, an enumeration of the edges that will be part of the shortest paths in the order they are discovered by the algorithm should give the following sequence of edges: Linkoping-Norrkoping Linkoping-Motala Motala-Akersund Linkoping-Jonkoping Akersund-Karlsborg Jonkoping-Alingsas Jonkoping-Goteborg Part B: Problem 1: ---------- A* maintains, for each node in the prioqueue: (i) actual discovered distance so far from Linkoping to node, and (ii) estimated distance from Linkoping to Goteborg via the node. It uses the estimated distances to pick cities from the prioqueue. It updates the actual distances as shorter ones are discovered. During execution, the "current" estimated distance to Goteborg passing by Motala is the shortest distance so far to Motala plus the estimated distance from Motala to Goteborg (can be read in the table to be 200). (prioqueue: Linkoping(cost: 0,prio: 0+224, via LKP)) -> (prioqueue: Motala(55,55+200,LKP),Jonkoping(128,128+130,LKP),Norrkoping(43,43+267,LKP)) * pick Motala(55,255,LKP) as has the smallest estimated distance from Linkoping to Goteborg: 255 (prioqueue: Motala(55,255,LKP),Jonkoping(128,258,LKP),Norrkoping(43,310,LKP)) -> (prioqueue: Jonkoping(128,258,LKP),Norrkoping(43,310,LKP), Akersund(103,103+213,MOT)) * pick Jonkoping(128,258,LKP) as has the smallest estimated distance from Linkoping to Goteborg: 258 (prioqueue: Jonkoping(128,258,LKP),Norrkoping(43,310,LKP), Akersund(103,103+213,MOT)) ->(prioqueue:Goteborg(276,276+0,J),Norrkoping(43,310,L),Akersund(103,316,M),Alingsas(253,253+41,J),Karlsborg(227,227+173,J)) * pick Goteborg(276,276,LKP) as it has the smallest estimated distance from Linkoping to Goteborg: 276 B.13 (4pts): The cities picked by A* are then: Linkoping, Motala, Jonkoping, Goteborg. Problem 2: ---------- B.14 (2pt): zigzig rotation from T1 gives: 192 154 147 /// 349 225 / 292 // 613 574 398 / 519 / 527 /// 930 688 628 // 928 /// B.15 (2pt): zigzag rotation from T1 gives: 688 613 349 192 154 147 /// 225 / 292 // 574 398 / 519 / 527 /// 628 // 930 928 /// Problem 3: ---------- B.Pb3.1 (2pt): elements: {613,349,930,574,192,688,154,398,628,519,225,527} tableau 1: row 0: 154,192,225,349 row 1: 398,519,527,574 row 2: 613,628,688,930 row 3: _ , _ , _ , _ tableau 2: row 0: 154,398,225,574 row 1: 192,519,527,613 row 2: 349,628,688, _ row 3: 930, _ , _ , _ B.Pb3.2.a(2pt) void insert(vector>& tableau, int i, int j) { if(i==0 && j>0){ //first row. Move to left if needed if(tableau[i][j-1] > tableau[i][j]){ swap(tableau[i][j-],tableau[i][j]); insert(tableau,i,j-1); } }else if(i>0 && j==0){//first column. Move up if needed if(tableau[i-1][j] > tableau[i][j]){ swap(tableau[i-1][j],tableau[i][j]); insert(tableau,i-1,j); } }else if(i>0 && j>0){//Move up or left if needed int max_row = i; int max_col = j; if(tableau[i-1][j] > tableau[i][j-1]){ max_row = i-1; max_col = j; }else if (tableau[i-1][j] < tableau[i][j-1]){ max_row = i; max_col = j-1; } if(tableau[max_row][max_col] > tableau[i][j]){ swap(tableau[max_row][max_col],tableau[i][j]); insert(tableau,max_row,max_col); } } } B.Pb3.2.b(2pt). When insert(tableau, i, j) is called, the tableau is sorted except possibly for position (i,j). The procedure moves the value (i,j) to the left or up in case it is strictly smaller than the value to the left or up. If it is smaller than both, then it is permuted with the largest one of them. The obtained tableau is sorted except possibly for the target of the permutation, on which insert is called again. If no swap is performed, then the value at (i,j) is larger or equal to the cell to the left and the cell up (if any). So the tableau is sorted. The value at position (i,j) may only move (if it moves) to the left or up. Each move corresponds to a constant amount of work and to a call to insert from the new position (i-1,j) or (i,j-1). In the worst case, the value has to be moved the whole way to (0,0). Hence, insert is Theta(N+M) where N is the number of rows and M the number of columns. B.Pb3.3.a (2pt). bool find(vector>& tableau, int key) { //start at the top right position int row = 0; int col = N-1; while(row < M && 0 <= col){ if(tableau[row][col] == key){ return true; } if(tableau[row][col] > key){ col = col - 1; }else{ row = row + 1; } } return false; } B.Pb3.3.b (2pt). Claim: in the loop after the first if statement, the key is not at any position to the right (i.e., higher or equal column index) or to the top (lower or equal row index) of the (row,col) position. This is true at the start after the test (as there are no positions to the right or to the top of (0,N-1). If the key is strictly larger than the current position, then it has to be at a larger row (i.e., below the current position) since all positions to the left at the same row are smaller. If the key is strictly smaller than the current position, then it has to be at a smaller column (i.e., to the left of the current position) since all positions below at the same col are larger. If we exceed the table because row==M or col==-1, then the key is not present. The loop might use at most M+N iterations (possible). A bounded amount of work is performed at each iteration. The procedure is therefore in Theta(M+N).