University of Manitoba COMP 3170, Winter 2018 Assignment 4 Solutions

Document Content and Description Below

University of Manitoba COMP 3170, Winter 2018 Assignment 4 Due Date: March 27, at 8pm “The natural flights of the human mind are not from pleasure to pleasure, but from hope to hope.” Samuel ... Johnson All problems are written problems; submit your solutions electronically via Crowdmark. Please read http://www.cs.umanitoba.ca/~kamalis/winter20/comp3170/course-info. pdf for guidelines on academic integrity. Problem 1 Amortized Analysis [10 marks] In the class, we saw a special type of stacks in which each operation involves popping n ≥ 0 items followed by pushing exactly one item. Consider a variant in which each operation involves popping one item followed by pushing n ≥ 0 items. Assume the stack is implemented using an array of fixed size C and the number of items in the stack is never more than C. Use the potential function method to show the amortized cost of each operation is at most 2. Define the potential to be the number of empty cells in the array, that is, if x is the number of items in the stack, the potential is C −x. Given an operation involving n pushes, the actual cost is n + 1; for each push, the potential is decreased by 1 unit (one less empty space). So, the difference in potential will be −n for pushed items and +1 for the pop, i.e., a total difference of −n+1 for the potential. The amortized cost will be (n+1)+ (−n+1) = 2. You get 5 marks for the right potential function and 5 marks for finding the right amortized cost. You get the full mark as long as you show the amortized cost is constant via a potential function argument. Problem 2 Union by Weight [10 marks] In this problem, we would like to show the amortized time of a union operation when unionby-weight on linked-lists is used is Ω(log n). For that, we nee [Show More]

Last updated: 1 year ago

Preview 1 out of 5 pages