\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{epsfig}
\usepackage{latexsym}
\begin{document}
\begin{center}
\bf
Algorithms\\
Computer Science 140 \& Mathematics 168\\
Instructor: B. Thom\\
Fall 2004\\
\rm
Homework 3a\\
Due on Thursday, 09/16/04 (beginning of class)\\
\end{center}
\begin{enumerate}
\item \textbf{[15] Prioritizing your Heap!}
In addition to serving as an efficient means for comparison-based sorting, 
heaps are also a great means for implementing a priority queue.
This problem deals with a {\em maximum} priority queue.
\begin{enumerate}

\item Give pseudo-code for {\tt Increase\_Key(i,key)} where
{\tt i} is the index in the heap of the element who's key is being changed, and
{\tt key} is the new value. You can assume that the function is only
called when {\tt key $\geq$ A[i]}.
Your pseudo-code should use a {\tt loop} (as opposed to recursion).



\item Prove that this algorithm is correct (restores the heap property to all
elements in the array). Be sure careful and precise: identify the appropriate loop invariant(s), 
use induction to demonstrate that this (these) invariant(s) are maintained,
clearly identify the base case, IHOP, and induction steps, and conclude by
reminding the reader of what aspect(s) of the invarient(s) you've just proved 
guarantee correctness. (Don't worry about demonstrating that the algorithm 
terminates.)




\end{enumerate}

\item \textbf{[10 Points]  Binary Counters with Reset!} CLRS Exercise
17.2-3 (page 412). Don't worry if your accounting scheme is overly generous with
putting rubles in the bank (you would only need to worry about this if it kept
you from demonstrating $\Theta(n)$).



\end{enumerate}
\end{document}
