Practice Exam 1 - Solutions

EE360C: Algorithms The University of Texas at Austin Exam #1 Dr. Santacruz September 22, 2022 Name: EID: Exam #1 No calculators, laptops, or other devices are allowed. This exam is closed book , but you are allowed to use a one-page, handwritten reference sheet. Write your answers on the test pages. If you need scratch paper, use the back of the test pages, but indicate where your answers are. Write down your process for solving questions and intermediate answers that may earn you partial credit. If you are unsure of the meaning of a specific test question, write down your assumptions and proceed to answer the question on that basis. When asked to describe an algorithm, you may describe it in English or in pseudocode. You can use results and proofs from class and homework without re-proving them, but make it clear when you are doing so (e.g., by saying “using the result from class that xyz...”). Similarly, you can use algorithms and data structures from class without re-explaining how they work. If you use a data structure or algorithm we haven’t covered in class, you will need to prove all relevant properties of it and explain how to implement it (you can’t take it for granted). If you write a correct answer but include additional incorrect information in response to a question, you will lose points. You have 75 minutes to complete the exam. The exam is 100 points total. Some sums we used in class, which you may or may not find useful: Series: n X k =1 k = 1 2 n ( n + 1) From computing the number of nodes in a full binary tree of height h : h X l =0 2 l = 2 h +1 − 1 From Building a Heap analysis: ∞ X k =0 k/ 2 k = 2 Log change of base formula: log b x = log a x log a b Log product rule: log a ( xy ) = log a x + log a y Log power rule: log a ( x p ) = p log a x

Exam #1: September 22, 2022 2 Problem 1: Stable Matching [25 points] (a) [12 points] Consider an instance of the stable matching problem where all applicants have the same position as their highest preferred position, call this position m ∗ . Let w ∗ be the top preference for m ∗ . Prove that every stable matching includes the pair ( m ∗ , w ∗ ). Solution Prove by contradiction. Suppose there a stable matching, S , that does not include the pair ( m ∗ , w ∗ ). In this matching m ∗ will be paired with a different applicant, w ′ and w ∗ will be paired with a different position, m ′ , creating the pairs ( m ∗ , w ′ ) and ( m ′ , w ∗ ), but m ∗ prefers w ∗ to w ′ and w ∗ prefers m ∗ to m ′ , which is an instability. This is a contradiction with the assumption that S is stable. (b) [13 points] Consider an instance of the stable matching problem where all applicants have the same position as the the lowest preferred position, call this position m ∗∗ . Let w ∗∗ be the applicant at the bottom of m ∗∗ ’s list. Prove or disprove the following statement: The Gale-Shapley algorithm will always return a match- ing that includes the pair ( m ∗∗ , w ∗∗ ). Solution The statement is not true. Consider the following counterexample, with preference lists: • a 1 : p 1 ≻ p 2 • a 2 : p 1 ≻ p 2 • p 1 : a 2 ≻ a 1 • p 2 : a 1 ≻ a 2 In this scenario, all applicants rank p 2 as their lowest preference, but when running GS, p 2 does not end up with a 2 , which is it’s worst preference. This is because p 1 ends up with a 2 since it’s highest preference. Problem 2: Asymptotic Notation [25 points] (a) [13 points] Let f ( n ) = n 2 − n + 1 and let g ( n ) = n 2 2 . Prove whether f ( n ) = O ( g ( n )), f ( n ) = Ω( g ( n )), f ( n ) = Θ( g ( n )), or all 3. Solution We will solve this problem using the limit theorems. We find the limit lim n →∞ n 2 − n + 1 n 2 / 2 = lim n →∞ 2 n − 1 n = lim n →∞ 2 1 = 2 . Since the limit is a constant, then f ( n ) = Θ( g ( n )), and by properties shown in class, it is also f ( n ) = O ( g ( n )) and f ( n ) = Ω( g ( n )), so it is all 3.

Exam #1: September 22, 2022 4 Problem 3: Decision Trees [25 points] Suppose I give you n diamonds, one of which is fake. The fake diamond can be identified easily because it weighs more than all of the others. Your goal is to find the fake diamond using a tradi- tional (balance) scale. You can place any number of items on each side of the scale. Any single use of the scale results in one of three outcomes: either the scale balances, the left hand side is heavier, or the right hand side is heavier. (a) [10 points] Use a decision tree to find lower bound on the number of weighings needed to determine which diamond is fake. Provide the lower bound in terms of n and justify your solution. Solution Any possible algorithm to solve this problem can be represented with a decision tree for any algorithm where each node represents a weighing and each node has 3 children, so we have a 3-ary tree. We have n diamonds and any of them could be the fake, we need a tree with n leaves, since our final decision could be any of the n diamonds. So we need a 3-ary tree with n leaves. The height of the tree represents the number of weighings. The smallest height the tree could have is log 3 ( n ). So our bound on the number of weighings required is log 3 ( n ) (b) [15 points] Design an optimal algorithm for determining the fake diamond in the fewest possible number of weighings. Solution Divide the n diamond into 3 sets of as close to equal amount of diamonds. Regardless of the value of n , there will always be 2 sets with the same number of diamonds. • If n mod 3 = 0, then all 3 sets have equal number of diamonds • If n mod 3 = 1, 2 sets have ⌊ n 3 ⌋ and one has ⌈ n 3 ⌉ • If n mod 3 = 1, 2 sets have ⌈ n 3 ⌉ and one has ⌊ n 3 ⌋ Weigh two sets with the same number of diamonds. If both sides are equal, the fake is in the set that was not weighed, otherwise it is on the the heavier side. Recursively work on the set of diamonds where the fake has been identified to be. Again divide the number of diamonds into three sets of approximately equal sizes, measure two sets with the same number of diamonds and repeat. Repeat until you have, at most 3 diamonds. If you have 3 diamonds, put 1 diamond on each side, if one is heavier that is the fake. If they are equal, the not weighed diamond is the fake. If you have 2 diamonds left, weigh one diamond on each side, the heavier is the fake. If you have 1 diamond left, that diamond is the fake.

Exam #1: September 22, 2022 5 Problem 4: Heaps [25 points] A d -ary heap is similar to the heap we saw in class, but with non-leaf nodes having up to d children instead of 2 children. In other words, in class we saw a heap as a balanced binary tree. A d -ary heap can be seen as a balanced d -ary tree. (a) [10 points] Describe how a d -ary could be represented in an array. In particular, for a given entry i in the array, where are the children of i ? Where is the parent of i ? ( Hint: This problem is easier is if you use 0-indexing ) Solution For entry i the children are in locations di +1 , di +2 , ..., di + d . The parent of i is at ⌊ i − 1 d ⌋ . (b) [15 points] Suppose you want to use the d -ary heap to sort an array. Let f ( n ) be the runtime of HeapSort using the d -ary heap. For sake of of comparison, let g ( n ) be the runtime of HeapSort using the binary heap we saw in class. Show whether f ( n ) = O ( g ( n )), f ( n ) = Ω( g ( n )), or f ( n ) = Θ( g ( n )). Solution Inserting into a d -ary heap is O (log d n ) and deleting the smallest element is also O (log d n ). Therefore, the runtime for HeapSort using a d -ary heap is f ( n ) = O ( n log d n ). From class, we know that HeapSort using a binary heap is g ( n ) = O ( n log 2 n ). From one of the Homework problems we know that all log of any base are Θ() or each other. Therefore in this case f ( n ) = Θ( g ( n )).