Arizona State UniversityCSE 5516-W2-Unit 3 Quiz solution

CSE 551 Graded Quiz 3 Solutions Jamison Weber June 2019 Question 1 For which of the following problems would amortized analysis be applicable? i.) Queue operations ii.) Sorting iii.) Stable Matching Correct Respo ...

CSE 551 Graded Quiz 3 Solutions Jamison Weber June 2019 Question 1 For which of the following problems would amortized analysis be applicable? i.) Queue operations ii.) Sorting iii.) Stable Matching Correct Response i. only Rationale There are not exactly well defined rules that determine which algorithms amortized analysis can be effectively applied to, but there are some patterns we should consider. In general, amortized analysis works best given some data structure and a set of operations that are repeated often. We consider two cases. The first case that allows us to amortize the cost of operations is when in the set of operations, there is some operation that does task X and another that undoes task X. For example, insert and delete. Consider the stack example. You can probably see why if we assume a more or less even distribution of push and pop operations over the stack, that on average, a call to multi-pop will cost something near constant time. The second case where amortization becomes applicable is when we can make rigorous predictions about the costs of future operations. Consider the dynamic array, specifically the case where you perform an insert operation that requires an array expansion (copying contents to another array twice as large as the previous). Continuous calls to this insert case will become twice as expensive relative to the last call, but occur half as often. You might be able to see how this intuitively averages out to a constant cost. See the table below for a complete list of amortized algorithms we have looked at in this class. 1With regard to stable matching and sorting, however, there are some concrete reasons why amortized analysis won’t give us any improved bounds. The main reason is that after a single call to sort, or a single call to propose-andreject, our problem instance is solved. We do not require any additional calls to these operations to solve their respective instances. The reason amortized analysis works on the examples above is that we can assume a distribution over a series of operations and we can make rigorous predictions about the cost of future operations, as seen with the case of the binary counter (i.e. bit position 3 flips every 4 calls, etc...). We cannot do anything like this with sorting or stable matching. There are other methods of calculating averages for sorting. For example, randomized quick-sort runs in O(n2) time in the worst case, but has an expected run time of O(nlogn). Calculating the expected run time of a randomized algorithm is not amortized analysis, but rather another technique called random analysis, which is not covered in this course. Amortized analysis has nothing to do with calculating probabilities and does not make any assumptions about the input. Question 2 Suppose you are tasked with performing the aggregate method to determine an amortized bound for an operation O whose cost function is defined below: Let k be the iteration index for the number of times O has been called. Cost(Ok) = k; if k is a power of 1; otherwise 3 What is the total cost T(n) of performing 27 iterations? Correct Response 63 Rationale We simply sum the cost function given over 27 iterations: 27 X k =1 Cost(k) = 1+1+3+1+1+1+1+1+9+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+27 2= 63 Question 3 From the following list, identify which of the following potential functions are valid. i.) The number of elements in a linear data structure ii.) The summation over the depth of each node in a binary heap iii.) The number of nodes minus the square of the tree-height of a binary search tree Correct Response i. and ii. Rationale We consider three criteria for the validity of a potential function Φ. a.) The function Φ reflects some quantifiable aspect of the data structure the operations are being applied to. b.) Φ(0) = 0. c.) Φ(i) ≥ 0 for all i > 0. Now we consider each potential function given: i. satisfies all of a,b,c. ii. satisfies all of a,b,c iii. satisfies a,b only. This function has negative values in its range. Consider the following binary search tree: