\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{latexsym}
\usepackage{textcomp} 
\usepackage{xcolor}
\usepackage{amsfonts,amsmath,amssymb}
\usepackage{fixltx2e} % Fixing numbering problem when using figure/table* 
\usepackage{booktabs}
\usepackage{times}
\usepackage{amssymb}\usepackage{times}
\usepackage{amssymb}
\usepackage{epic}
\usepackage{eepic}
\usepackage{graphicx}
\usepackage{epstopdf}
\usepackage[hmargin=.75in,vmargin=1in]{geometry}
\usepackage[american]{babel}
\usepackage[T1]{fontenc}
\usepackage{caption}
 
\usepackage{textcomp}
\usepackage{xcolor}
\usepackage{amsfonts,amsmath,amssymb}
\usepackage{fixltx2e} % Fixing numbering problem when using figure/table* 
\usepackage{booktabs}
\usepackage{epic}
\usepackage{eepic}
\usepackage{graphicx}
\usepackage{epstopdf}
\usepackage[hmargin=.75in,vmargin=1in]{geometry}
\usepackage[american]{babel}
\usepackage[T1]{fontenc}
\usepackage{caption}
 
  
\pdfminorversion=4

 
\DeclareGraphicsRule{.tif}{png}{.png}{`convert #1 `basename #1 .tif`.png}
 
\pdfminorversion=4

%% NOTE: The following line inserts the graphic file heap.pdf, of width 4.2 inches, to the text
%\centerline{\includegraphics[width=4.2in]{heap}}



\begin{document}
\begin{center}
{ \Large \bf CMPU 241 - Analysis of Algorithms}\\
  {\bf Spring 2020 \\
 Assignment 3\\
 Due: Thursday, February 20$^{th}$, by 5 pm\\}
  \vspace{.15in}
NAME: (1 point)\underline{\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }\\

\end{center}


\vspace{.25in}



\begin{enumerate}

\item (2 points) Use induction to show that the actual number of nodes at level $l$ of a full and complete binary tree  is $2^l$. Recall that the root is at level 0.\\

\vspace{2in}

\item (3 points) Use induction to show that the actual number of nodes in a full and complete binary tree of height $h$ is $2^{h+1} - 1$, where $h$ is the height of the tree.\\

\vspace{2in}


\item (4 points) What are the minimum and maximum numbers of nodes in a heap of height $h$, for $h >0$? Explain your answers, possibly using the proofs from problems 1 and 2.\\


\newpage



\item (5 points) Assume the following sequence of numbers is arranged in level-order numbering in an array like the one shown in Figure 6.1 of your text.  

Is the sequence $\langle 27, 15, 14, 6, 13, 10, 11, 5, 7, 17\rangle$ a max-heap?  List the numbers in each level of the tree formed by the sequence (or draw a tree) and either describe what makes it a max-heap or point out where it violates the properties of a max-heap.  If it is not a max-heap, indicate how many exchanges of values would be necessary to make it a max-heap and where those exchanges would occur. If applicable, list the numbers in each level of the tree formed by the new sequence (or draw the tree again).\\

\vspace{5.5in}






\item (5 points)  If $A[p]$ was always chosen as the pivot in line 1 of QuickSort's {\sc Partition} function (given on page 
171 of our textbook), would it change the worst-case running time of QuickSort? Answer "yes" or "no" and {\it explain your answer}.

\vspace{2in}


\newpage

\item(10 points) This Question is similar to Problem 7-1, on page 185 of our textbook. Suppose the array A is of 
length $n$ and this algorithm
takes $(A, 1, n)$ as initial input.\\

{\tt
\begin{center}
\begin{tabular}{l l}
\multicolumn{2}{l} {{\sc Hoare-Partition}(A,p,r):}\\
\ 1. & $x = A[p]$ \ \ \ \ \ \ \ \\
\ 2. & $i = p-1$\\
\ 3. & $j = r+1$\\
\ 4. & {\bf while} {\sc TRUE}\\
\ 5. &\hspace{5mm} {\bf repeat} \\
\ 6. &\hspace{10mm} $j = j - 1$\\
\ 7. &\hspace{5mm} {\bf until} $A[j] \leq x$\\
\ 8. &\hspace{5mm} {\bf repeat} \\
\ 9. &\hspace{10mm} $i = i + 1$\\
10. &\hspace{5mm} {\bf until} $A[i] \geq x$\\
11. &\hspace{5mm} {\bf if} ($i < j$)\\
12. &\hspace{10mm} exchange $A[i]$ with $A[j]$\\
13. &\hspace{5mm} {\bf else}\\
14. &\hspace{10mm} {\bf return} $j$\\
\end{tabular}
\end{center}
}


Demonstrate the operation of {\sc Hoare-Partition} on the array\\ 

\hspace{1.5in}$A = \langle 13,\ 19,\ 9,\ 5,\ 12,\ 8,\ 7,\ 4,\ 11,\ 2,\ 6,\ 21 \rangle$\\ 

showing the values of the array and auxiliary values
$i$ and $j$ after each iteration of the {\bf while} loop in lines 4--14 and when the procedure returns. 
Your depiction of the algorithm
operation should be like that shown on page 172 of our textbook for the operation of {\sc Partition}, an algorithm 
given
in our textbook on page 171.

\end{enumerate}


\end{document}



