CSC263H1, Fall 2019 Problem Set 5 Sample Solutions
CSC263H1: Problem Set 5 Sample Solutions
Due Tuesday November 5 before 10pm
Note: solutions may be incomplete, and meant to be used as guidelines only. We encourage you to ask followup questions on the course forum or during office hours.
1. 10 marks Amortized analysis: Binomial Heaps
a 10 marks Using the accounting method, prove that in a binomial heap, the amortized cost of BINOMIALHEAPINSERT is in O1 and amortized cost of BINOMIALHEAPEXTRACTMIN is in Ologn, where n is the number of elements in the binomial heap. Only consider sequences containing insert and extractmin operations.
In your analysis, let 1 denote the maximum of:
the time to create a binomial heap with one element,
the time to compare the sizes of two binomial trees, the value of their roots, and link them
together, and
the time to update enough pointers to move a tree from one linked list to another.
Your solution should include at least a clearly stated credit invariant, and clear arguments that the invariant is maintained by the operations.
Solution
We maintain the credit invariant that every tree in the binomial heap forest has 1 credit. This is analogous to having 1 credit on each 1 bit in a binary counter.
We prove the invariant by induction.
Base case: The invariant holds for the empty binomial heap.
Inductive case for Insert: Assume the invariant holds prior to Insert. We prove it holds after Insert.
Insert H, x
1: insert new tree containing x into H
2: s1
3: while H contains two trees of size s
4:link two trees
5: s2s
2 charge
2 credit1 cost1 credit
2 credit1 cost1 credit
We charge 2 for Insert this is an O1 charge. The invariant holds prior to Line 1, by inductive hypothesis. Line 1 consumes 1 to create a tree, leaving 1 credit on the new tree. Therefore the invariant is fulfilled after line 1.
Therefore, prior to the first iteration of Line 4, the invariant holds. We show that if it holds prior to an iteration, it must hold after the iteration. Line 4 considers two trees, therefore, by the credit invariant, 2 credit is available. It costs 1 to link to trees into a single tree, leaving 211 credit for the resulting tree. Therefore the invariant holds after each iteration of Line 4. Q.E.D.
Inductive case for ExtractMin: Assume the invariant holds prior to ExtractMin. We prove it holds after ExtractMin.
BINOMIALHEAPEXTRACTMINH takes Olog n time. The resulting binomial heap con
tains at most log2 n trees, so it costs at mostlog2 n to reestablish the credit invariant after the operation. Thus, the amortized cost of this operation is in Olog n.
Page 15
CSC263H1, Fall 2019 Problem Set 5 Sample Solutions
Page allowance: Please neatly present your solution using 12 pages. Any additional pages will not be marked.
Page 25
CSC263H1, Fall 2019 Problem Set 5 Sample Solutions
2. 15 marks Amortized analysis: Sets
Consider the following data structure for representing a dynamic set, supporting only search and insert operations. The elements of the set are stored in a singly linked list of sorted arrays, where the number of elements in each array is a power of 2 and the sizes of all the arrays in the list are different. Each element in the set occurs in exactly one array. The arrays in the linked list are kept in order of increasing size.
To perform SEARCH, perform binary search separately on each array in the list until either the desired element is found or all arrays have been considered.
To insert a new element x into the set given the precondition that x is not already in the set,
a create a new array of size 1 containing x
b insert this new array at the beginning of the linked list
c while the linked list contains 2 arrays of the same size, merge the 2 arrays into one array of twice the size
a 5 marks What is the worstcase time, to within a constant factor, for performing SEARCH when the set has size n? Justify your answer.
Solution
Let In denote the set of bit positions in the binary representation of n that contain the value 1. Then the worstcase time to perform SEARCH is ini.
iIn
In the worstcase, binary search may have to be performed on each array in the linked list. If
an array has size 2i, then binary search on that array takes Oi time for i0. There is an array in the linked list of size 2i if and only if iIn. Thus, the worstcase time complexity for SEARCH is in O i.
iIn
When the element being sought is not in the list, binary search will be performed on each array in the list and will take time proportional to the logarithm of the size of the array. Thus, the worstcase time complexity for SEARCH is ini.
iIn Inthecasethatn2k1forsomeintegerk1,In 0,…,k1andthetotaltimetaken
k1
is inik2log n2.
i0
Page 35
CSC263H1, Fall 2019 Problem Set 5 Sample Solutions
b 5 marks What is the worstcase time, to within a constant factor, for performing INSERT when the set has size n? Justify your answer.
Solution
Let vn denote the largest power of 2 that divides n1. Then the linked list contains arrays of
size 1,2,4,8,…,2vn1, but no array of size 2vn.
When INSERT is performed on a set of size n, the while loop is performed vn1 times. The
kth time through the loop, we merge an array of size 2k containing the newly created inserted
element with an existing array of the same size. This takes 2k time. Thus the total time is vn 1
in 2i2vn . i0
In particular, when n2k1, for some integer k1, then vnk, so the total time taken is in 2kn.
Page 45
CSC263H1, Fall 2019 Problem Set 5 Sample Solutions
c 5 marks Use the accounting method to prove that the amortized insertion time in a sequence of n insertions, starting with an initially empty set, is log n.
Solution
Let 1 credit be sufficient for two element assignments, including allocating the required space. The credit invariant is that the number of credits in each nonempty array is at least the number of elements in all smaller nonempty arrays. For example, if there is an array of size 1, an array of size 2, and an array of size 8, the array of size 2 contains at least 1 credit and the array of size 8 contains at least 3 credits.
Initially, the credit invariant is vacuously true, since there are no nonempty arrays.
Let the amortized cost of each insertion be 2log2 n. The cost to create a new array of size 1 containing x is 1. Allocate 1 credit to each of the other nonempty arrays. Since there are at most 1log2 n existing arrays, there are sufficient credits to do this.
If the array containing x is merged with an array A of length 2i, then, before the insertion, there were 2i1 elements in smaller arrays. This implies that A contains 2i credits, one for each of these elements in smaller arrays, plus one from the insertion of x. These credits can be used to pay for the merge of A with the 2i element array containing x. Note that we need only 2i credits to pay for merging 22i elements.
There are no elements in any smaller arrays after this merge, so the invariant is vacuously true for the resulting array.
Each array that is not involved in a merge during this insertion also satisfies the invariant, since it was given one additional credit and only one element was added to the set of elements in smaller arrays.
Thus the credit invariant is true after each INSERT operation. It follows that the amortized insertion time in a sequence of n insertions, starting with an initially empty set, is Olog n.
Page allowance: Please neatly present your solution using 12 pages. Any additional pages will not be marked.
Page 55
Reviews
There are no reviews yet.