Exam3-PlanD-Solutions

CMSC351 Fall 2022 Exam 3 Make up Plan D - Solution NAME (Neatly): UID (Neatly): Instructions: Please do all problems on the pages and in the spaces provided. This exam will be scanned into Gradescope and if your answers are not in the correct locations they will not be found or graded!

. THIS PAGE INTENTIONALLY LEFT BLANK! DO NOT USE!

3. We are using counting sort to sort an array of numbers. Fill in the blanks: Array to be sorted [10 pts] index 0 1 2 3 4 5 6 value 3 4 0 2 4 Helper array after 1st step index 0 1 2 3 4 value Helper array after 2nd step index 0 1 2 3 4 value 3 7 Solution: Array to be sorted index 0 1 2 3 4 5 6 value 3 4 0 0 0 2 4 Helper array after 1st step index 0 1 2 3 4 value 3 0 1 1 2 Helper array after 2nd step index 0 1 2 3 4 value 3 3 4 5 7

4. We are using radix sort to sort an array of integers; below is the run of it but with one or more errors. List all the errors in the run of the algorithm: [10 pts] Numbers 3456 1278 4567 3980 3237 9876 Step 1 3980 3456 9876 3237 4567 1278 Step 2 3237 3456 4567 1278 9876 3980 Step 3 1278 3237 3456 4567 9876 3980 Step 4 1278 3237 3456 3980 4567 9876 Step 5 Step 6 Solution: 3237 and 4567 were swapped in Step 1 1278 and 9876 were swapped in Step 2 1278 and 3237 were swapped in Step 3

6. We have the following adjacency matrix for an undirected graph. Run Dijkstra’s algorithm using starting vertex A. Keep track of the pred list. Fill in the table below. The last column (”Order”) is the order in which the vertices are added to S (obviously, the source vertex, A, is added first). Only values in the array will be scored. Anything written elsewhere will be considered scratch work). Vertex A B C D E F A 0 15 11 4 INF INF B 15 0 INF INF 2 6 C 11 INF 0 3 1 INF D 4 INF 3 0 INF 2 E INF 2 1 INF 0 3 F INF 6 INF 2 3 0 [15 pts] Vertex Distance Predecessor Order A 0 None 1 B C D E F Solution:

Vertex Distance Predecessor Order A 0 None 1 B 10 E 6 C 7 D 4 D 4 A 2 E 8 C 5 F 6 D 3 7. We are using the MOM method to select a pivot before running partition on an array of exactly 99 elements. We are using small sublists of 9 (NOT 5) elements each. What is the minimum size of the sublist on which we will make a recursive call to kthSmallest after partition is run? [5 pts] Solution: (4 + 1)(5 + 1) − 1 = 29 8. An algorithm has a running time satisfying the following recurrence relation: T ( n ) = T (0 . 4 n ) + T (0 . 59 n ) + Θ( n ) What is the Θ of T ( n )? No proof needed. DONE [3 pts] Solution: Θ( n ) 9. Suppose the list A contains n 3 integers between 0 and n − 1 inclusive, each represented in [6 pts] decimal. What is the time complexity of RadixSort+CountingSort applied to such a list? Solution: Θ( n 3 logn )