[2022] COMP 3170 Assignment 4 - Skip List
COMP 3170 Assignment 4
[10 marks]
Problem 1 Describe how a skip list can be augmented so that the select operation can be supported in O(log n) time for a dictionary of n keys. Your answer should include the following:
1. what extra information is stored at each node
2. how the extra information is updated after an insert delete (without in- creasing the complexity of these operations)
3. how to perform the select operation in O(log n) time using the augmented data structure.
Be precise and detailed in your answer.
[5 + 5 marks]
Problem 2 Consider a skip list in which we build new towers with probability 5/6. More precisely, when adding an element to the skip list, we repeatedly roll a die with 6 sides until we get a“6”. The number of times we roll the die defines the height of the tower (so if the first number we roll is a 6 then the tower has height 1). We will assume that the numbers 1 to 6 all have the same chance of appearing.
(a) What is the expected space complexity (using asymptotic notation) of the modified skip list? Justify your answer.
(b) What is the running time of the search operation in the modified skip list? Justify your answer.
[3 + 3 + 5 + 5 marks]
Problem 3 Consider the following definition of a trinomial tree:
• A trinomial tree of order 0 is a single node
• A trinomial tree of order i is formed by taking three copies of trinomial trees of order i − 1 nad letting the root of one tree have the other two trees as its first and second children (see the figure below).
(a) Draw the trinomial tree of order 3.
(b) Is the following statement correct? Briefly justify your answer.
Let Ti denote the trinomial tree of order i. The children of the root of Tk are the trionial trees Tk − 1 ,Tk −2 , ··· ,T1 ,T0 . (An equivalent statement is that there is exactly one copy of each Ti as a child of Tk for i ≤ k − 1.)
(c) How many nodes exist in a trinomial tree of order k? You should provide a recursive formula and solve it. (A proof that your closed form is correct is not necessary)
(d) What is the height of a trinomial tree of order k? Again, you should provide a recursive formula and solve it. (A proof that your closed form is cor- rect is not necessary)
[10 marks]
Problem 4 In 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 exactly 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.
[10 marks]
Problem 5 In this problem, we will show that the amortized cost of a union operation for linked-lists with union-by-weight is Ω(log n). To do that, we need to come up with a sequence of Θ(n) operations for which the amortized cost per operation is Ω(log n). We start with make-set(xi ) for i ∈ {1, ··· ,n}. Provide a consequent sequence of Θ(n) union operations so that the total number of updated pointers for all operations is Ω(nlog n). You may assume that n is a power of 2.
[BONUS, maximum of 10 marks]
Problem 6 Describe how a Fibonacci heap can be augmented to support the prune operation (described below). Use the potential function method to ana- lyze the amortized cost of all Fibonacci heap operations seen in class and the amortized cost of the prune operation. Your augmentation should not increase the amortized cost of the Fibonacci heap operations seen in class.
