算法代写 | COMP 3804/MATH 3804 Design and Analysis of Algorithms I Assignment 2

本次加拿大代写是算法分析与设计的一个assignment

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 efficiently. Describe your algorithm in sufficent
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?