Exam1C_Solutions

Pennsylvania State University — CMPSC465 : Data Structures & Algorithms Exam 1 Lecturers: Antonio Blanca and Yana Safonova September 22, 2023 Exam 1 - C Name: Penn State access ID (xyz1234) in the following box: Student ID number (9XXXXXXXX): TA and/or section time: Instructions: • Answer all questions. Read them carefully first. Be precise and concise. Handwriting needs to be neat. Box numerical final answers. • Please clearly write your name and your PSU access ID (i.e., xyz1234) in the box on top of every page . • Write in only the space provided. You may use the back of the pages only as scratch paper. Do not write your solutions in the back of pages! • Do not write outside of the black bounding box : the scanner will not be able to read anything outside of this box. • We are providing two extra page at the end if you need extra space. Make sure you mention in the space provided that your answer continues there. Good luck! 1

Name: PSU Access ID (xyz1234): Multiple choice questions (27 points) For each of the following questions, select the right answer by filling the corresponding grading bubble grading bubbles. 1. Run Build-Heap on the array [3 , 5 , 4 , 8 , 6 , 2 , 10 , 1 , 8 , 11] to construct a min heap. Select the resulting min heap. 1 2 6 11 8 5 8 3 10 4 (d) 1 3 5 8 8 6 11 2 4 10 (e) 1 3 5 4 10 6 11 2 8 8 (f) 2 3 5 8 10 8 6 4 1 11 (a) 3 5 8 8 6 11 2 4 10 1 (b) 1 2 6 8 10 5 11 3 4 8 (c) Answer. ○ (a) ○ (b) ○ (c) ○ (d) '! (e) ○ (f) 2

Name: PSU Access ID: 3. Consider the min heap on the left below. Suppose that first the element at position 3 of the array is removed from the heap (remember that we use 0 indexed arrays), and after that the element at position 1 is removed from the heap. 3 6 7 10 12 8 14 12 5 9 13 10 7 Which one of the following is the resulting min heap? 3 8 10 12 12 14 5 9 13 10 7 (a) 3 13 10 10 12 8 14 12 5 9 7 (b) 3 8 10 10 12 12 14 13 5 9 7 (c) 3 8 10 13 12 10 14 12 5 9 7 (d) Answer. ○ (a) ○ (b) '! (c) ○ (d) ○ (e) 4

Name: PSU Access ID: 4. The array [ 1 , 4 , 3 , 8 , 9 , 12 , 16] corresponds to a min heap. In the space provided below, write down the resulting heap (as an array) after the first two iterations of the heapsort algorithm. Answer. ○ [ 8 , 9 , 12 , 16 , 4 , 3 , 1] '! [ 4 , 8 , 12 , 16 , 9 , 3 , 1] ○ [ 16 , 4 , 12 , 8 , 9 , 3 , 1] ○ [ 1 , 4 , 3 , 8 , 9 , 12 , 16] ○ [ 12 , 4 , 16 , 8 , 9 , 3 , 1] ○ [ 1 , 3 , 4 , 8 , 9 , 12 , 16] 5. How many integer multiplications does Strassen’s algorithm need to do to multiply two 4 × 4 matrices of integers? Answer. ○ 9 ○ 8 ○ 64 '! 49 ○ 16 ○ 7 6. Suppose that lim n →∞ f ( n ) g ( n ) = ∞ . Which of the following must be true? Answer. ○ f ( n ) = O ( g ( n )) '! f ( n ) = Ω( g ( n )) ○ f ( n ) = Θ( g ( n )) ○ None of the above. 7. What is the running time of Insertion Sort (for sorting in ascending order) on a list with the first n −⌈ √ n ⌉ elements sorted in ascending order? Answer. ○ O ( √ n ) ○ O ( n log n ) ○ O ( n 2 ) '! O ( n 3 / 2 ) ○ O ( n ) 5

Name: PSU Access ID (xyz1234): True/False (20 points) True or false? Fill in the correct bubble. No justification is needed. No points will be subtracted for wrong answers, so it is in your best interest to guess all you want. T F ○ ○ n 0 . 25 = O ((log n ) 5 ). False ○ ○ n 2 n = O (3 n ). True ○ ○ n log n = Ω(2 n ). False ○ ○ If f ( n ) and g ( n ) are non-negative functions, then either f ( n ) = O ( g ( n )) or g ( n ) = O ( f ( n )). False Explanation: Consider f ( n ) = 1 when n is even and n 2 when n is odd. Let g ( n ) = n . Then, we can see that f ( n ) ̸∈ O ( g ( n )) and g ( n ) ̸∈ O ( f ( n )). ○ ○ If f ( n ) = O ( g ( n )), then there is some value of n where f ( n ) ≥ g ( n ). False Explanation: Consider f ( n ) = n and g ( n ) = n + 1. Clearly f ( n ) = O ( g ( n )). But there is no value of n for which f ( n ) ≥ g ( n ). ○ ○ The procedure Heapify-Down could make O (1) swaps only. True Explanation: This asks about a possible case and not a general case. ○ ○ In a min heap, the largest element will be stored in the last position of the array. False ○ ○ In a min heap, the left child of the root is larger than the root. False ○ ○ Checking whether a min heap with n elements contains a certain element takes O (log n ) time. False Explanation: There is no order between the left and right children of each node. ○ ○ ∑ n i =1 4 i = O (4 n ) . True 7

Name: PSU Access ID: Recurrences (12 points) Each of the following scenarios outlines a divide-and-conquer algorithm. In each case, write down the appropriate recurrence relation for the running time as a function of the input size n and give its solution. Giving your solution in O -notation suffices. You need not give a full derivation of your solution, but you should indicate how you arrived at it (e.g., by using the Master Theorem). You may assume that n is of some special form (e.g., a power of two or of some other number), and that the recurrence has a convenient base case with cost Θ(1). (a) An input of size n is broken down into 9 subproblems, each of size n/ 3. The time taken to construct the subproblems, and to combine their solutions, is Θ( n 2 ). Solution: In this case, T ( n ) = 9 T ( n/ 3) + O ( n 2 ). Using the Master Theorem ( a = 9 , b = 3 , d = 2), we get log b a = log 3 9 = 2 = d , so T ( n ) = O ( n 2 log n ). (b) An input of size n is broken down into √ n subproblems, each of size √ n . The time taken to construct the subproblems, and to combine their solutions, is n . Solution: T ( n ) = √ nT ( √ n ) + n . This was essentially Problem 5j from Homework 3, and if you remembered the solution, it was fine to justify as “this was a HW problem”. Alternatively, you can note by unfolding that T ( n ) = n 1 2 + 1 4 + ··· + 1 2 k + kn = T ( n 1 2 k ) + kn Now if we let k = log 2 log 2 n , we have n 1 2 k = 2 which is constant. Since 1 2 ≤ 1 2 + 1 4 + · · · + 1 2 k ≤ 1, we have T ( n ) = Θ( n log log n ) . 8

Name: PSU Access ID (xyz1234): 10

Name: PSU Access ID (xyz1234): 11