cse332-midterm-23au

University of Washington cse332: Data Structures and Parallelism 25 January 2024 CSE 332 Midterm Exam Autumn 2023 Name Answer Key Net ID Academic Integrity: You may not use any resources on this exam except for writing instruments, your own brain, and the exam packet itself. This exam is closed notes, closed neighbor, closed electronic devices, etc.. The last two pages of this exam provide a list of potentially helpful identities as well as room for scratch work (respectively). No markings on these last two pages will be graded. Your answer for each question must fit in the answer box provided. Instructions: Before you begin, Put your name and UW Net ID at the top of this page. Make sure that your name and ID are LEGIBLE. Please ensure that all of your answers appear within the boxed area provided. Section Max Points ADTs and Data Structures 10 Asymptotic Analysis 16 Priority Queues and Heaps 14 AVL Trees 10 B Trees 10 Tries 5 Extra Credit (+1.3) Total 65

cse332 Autumn 2023 2 CSE 332 Midterm Exam Section 1: ADTs and Data Structures (4 pts) Question 1: For each of the following, indicate whether it is a Data Structure or an Abstract Data Type by writing DS or ADT (respectively) in the box provided. (a) Trie: (b) Heap: (c) Dictionary: (d) List: (2 pts) Question 2: Alaska Airlines wants to build a system for managing calls to the customer support call center. The system allows users to leave a phone number, and the next available agent will later return the customers’ calls in the order received. What ADT below should the system use to store the phone numbers? Indicate the letter of your choice in the box. A. Stack B. Priority Queue C. Queue D. Dictionary (4 pts) Question 3: In 1 or 2 sentences, describe one reason why you might use a B Tree over an AVL Tree. Creative Commons BY-NC 4.0 Nathan Brunelle

cse332 Autumn 2023 4 CSE 332 Midterm Exam (a) Begin by sketching the tree in space below. For full credit, you must include at least the first 3 levels of the tree (i.e. the root, its children, and its grandchildren), and it should be clear what the input size is for each recursive call. (b) Indicate exactly the total amount of work done at level i of the tree (define the root to be level 0 ). Include all constants and non-dominant terms. (c) Indicate the level of the tree in which the base cases occur. (d) Give the total work across the base case level (i.e. the leaves of the tree). Include all constants and non-dominant terms. (e) Give a summation to express the total work. Include all constants and non-dominant terms. (f) Finally, give a simplified Θ bound on the solution to the sum. (You do not need to show your work.) Θ ( ) Creative Commons BY-NC 4.0 Nathan Brunelle

cse332 Autumn 2023 5 CSE 332 Midterm Exam Section 3: Priority Queues and Heaps (6 pts) Question 7: Answer the following questions about the given binary heap. Note that we have not identified the priority of the item at index 4 and it instead has x as a placeholder. Indices 12, 13, 14, and 15 are not yet occupied. The empty space below is available if you would like to draw the heap as a binary tree. This drawing is optional and it will not be graded. (a) What is the smallest integer value for x which would cause the heap property to hold? (b) Give an integer priority that, when added to the heap, would result in exactly 2 swaps during the percolate up procedure. (c) Suppose the priority x was changed to be 0 in the original tree provided, what would be found at index 4 after the heap property was restored using percolate up/down? Creative Commons BY-NC 4.0 Nathan Brunelle

cse332 Autumn 2023 7 CSE 332 Midterm Exam Section 4: AVL Trees (6 pts) Question 11: Answer the following questions about the AVL Tree below. Each question should be considered completely independently (i.e. "reset" to the image between questions). (a) Give a integer key which, when inserted into the given AVL tree, would cause a double rotation. (b) Insert the key 6 into the original tree drawn above, what node will become the root of the tree? (c) Insert the key 11 into the original tree drawn above, identify the parent of the node with key 27 . (4 pts) Question 12: Describe (in 1 or two sentences) a Θ( n ) running time algorithm which prints all elements of a given non-empty AVL Tree in descending order (item with the largest key printed first, smallest key last). Creative Commons BY-NC 4.0 Nathan Brunelle

cse332 Autumn 2023 8 CSE 332 Midterm Exam Section 5: B Trees (2 pts) Question 13: Suppose we had a B Tree with L = 6 and M = 10 that contains 60 items. What is the minimum height of this tree? (Recall that we define height to be the maximum number of edges between the root and a leaf) (2 pts) Question 14: Suppose we had a B Tree with L = 6 and M = 10 that contains 60 items. What is the maximum height of this tree? (6 pts) Question 15: Answer the following questions about the B tree below. (a) What is L ? (b) What is M ? (c) Insert the keys 8 , 9 , 10 in that order, then draw the resulting tree below Creative Commons BY-NC 4.0 Nathan Brunelle

cse332 Autumn 2023 10 CSE 332 Midterm Exam Section 7: Extra Credit (+0.65 pts) Question Extra 1: In the space below, draw a picture of how you were feeling coming into this exam. (+0.65 pts) Question Extra 2: Now draw a picture of how you are feeling coming out of it. Creative Commons BY-NC 4.0 Nathan Brunelle

cse332 Autumn 2023 11 CSE 332 Midterm Exam Identities Nothing written on this page will be graded. Summations ∞ YYYYYYY i =0 x i = 1 1 − x for | x | < 1 n − 1 YYYYYYY i =0 = i =1 YYYYYYY n = n n YYYYYYY i =0 i = 0 + i =1 YYYYYYY n i = n ( n + 1) 2 n YYYYYYY i =1 i 2 = n ( n + 1)(2 n + 1) 6 = n 3 3 + n 2 2 + n 6 n YYYYYYY i =0 i 3 = n ( n + 1) 2 2 = n 4 4 + n 3 2 + n 2 4 n − 1 YYYYYYY i =0 x i = 1 − x n 1 − x n − 1 YYYYYYY i =0 1 2 i = 2 − 1 2 n − 1 Logs x log x ( n ) = n a log b ( c ) = c log b ( a ) log b ( a ) = log d ( a ) log d ( b ) Creative Commons BY-NC 4.0 Nathan Brunelle