This homework assignment is about backtracking and max$-$heaps. You may write procedures in a programming language or in Cormen$$s pseudocode. Make sure you know how Cormen$$s pseudocode works before you begin this assignment: it may work differently from what you expect.

$$

$1.$ Questions $1$a and $1$b are about searching for an element in a max$-$heap. Unlike binary search trees, heaps are not designed to be searched. However, it is still possible to search heaps somewhat efficiently by using their mathematical properties.

$1$a$.(10$ points.$)$ Suppose that A is an array whose integer elements are organized into a max$-$heap, and that e is an integer. Write a procedure IN$-$MAX$-$HEAP$($A$,$e$)$ that returns TRUE if e is an element of A$,$ and returns FALSE otherwise. You may use one or more $$helper$$ procedures. Your procedures must not change A$.$ They must not copy A$.$ They must not use linear search. They must not visit all elements of A if possible.

$1$b$.(10$ points.$)$ Can the run time of IN$-$MAX$-$HEAP from question $1$a be determined by the master theorem? There are three possible answers, depending on what you think $$run time$$ means.

The master theorem can always be used.

The master theorem can sometimes be used.

The master theorem can never be used.

Choose the answer that you think is correct, and explain why you chose it$.$

$2.$ Questions $2$a and $2$b are about the backtracking procedure MAKE$-$SETS and its helper MAKING$-$SETS, written in Cormen$$s pseudocode. The symbol $$ is the empty set, and the symbol $$ is the set union operator. The parameters n$,$ k$,$ and e are nonnegative integers. The parameter s is a set of nonnegative integers.

MAKE$-$SETS$($n$,$k$)$

$$MAKING$-$SETS$($n$,$k$,1,)$

$$

MAKING$-$SETS$($n$,$k$,$e$,$s$)$

$$if$$k$==0$

$$print$$s$$

$$else$$

$$for$$e$=$e$$to$$n$$

$$MAKING$-$SETS$($n$,$k$1,$e$+1,$s$\{$e$\})$

$2$a$.(5$ points.$)$ What will MAKE$-$SETS$(4,3)$ print? Hint: enumerate calls to MAKING$-$SETS breadth$-$first.

$2$b$.(5$ points.$)$ Suppose that n and k are nonnegative integers. What does MAKE$-$SETS$($n$,$k$)$ compute? Your answer must be one short sentence, stated in terms of n and k$.$