# 算法代写 | 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 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?