Question 1:[10 points]
Consider you are given a heap, called n heap, on n = 28 elements and a heap, called k heap, on
k=9 elements. Show the descriptors for the pennant forests correspoding to the two heaps. Show
the descriptor for the pennant forest for the heap, called n + k heap, resulting from applying
the operation merge two heaps discussed in class (see also the paper on the course web-page).
Illustrate, step by step, how the merge operations works, if we are only! concerned about the
heap shape, i.e., NOT the heap order.
Question 2:[10 points]
The linear-time algorithm for selection discussed in class groups the n input elements into n=5
groups of 5 elements each. Does a grouping into n=9 groups of 9 elements each, or n=3 groups of
3 elements each, work? Argue exactly why, or why not, by reworking for these two instances the
analysis carried out in class.
Question 3:[10 points]
Suppose you want to support the operation DeleteAnyElement(pointer into the heap to the ele-
ment to be deleted) in a heap. You must do this efﬁciently. Describe your algorithm in sufﬁcent
and establish its correctness.
Question 4:[10 points]
Consider a permutation of the numbers 1, …, n as input to the following algorithm:
Initialize an empty stack;
For each input value x:
While the stack is nonempty and x is larger than the top item on the stack do
pop the stack to the output
Push x onto the stack
While the stack is nonempty do pop it to the output
What is the sequence of POP/PUSH operations executed on input permutations:
a) 3214 b) 4123 ?
Find all permutations of 4 input elements that the algorithm does not sort correctly? What
happens in this case? Characterize the permutations (i.e., see a pattern) in your own words?
本网站支持 Alipay WeChatPay PayPal等支付方式
E-mail: email@example.com 微信号:vipnxx