Consider a sequence of $n$ operations on a data structure. For each $i$ in $\{1,$dots,$n\},$ operation $i$

has cost $c_i>0$ and takes the data structure from state $D_{i-1}$ to state $D_i.$ Let $$ be a potential function

that maps any given state of the data structure to a $($possibly negative$)$ real number.

$($a$)$ Write down an expression for the amortized cost hat$(c{)}_i$ of operation i with respect to potential function $.$

$($b$)$ Develop an exact expression for the total actual cost of the $n$ operations in terms

of the following three quantities: $(1)$ the total amortized cost of the $n$ operations; $(2)(D_0)$;

$(3)(D_n).$

$($c$)$ We say that potential function $$ is valid if $(D_0)=0$ and $(D_i)0$ for all $i$ in

$\{1,$dots,$n\}.$ Prove that if $$ is valid, then the total actual cost of the $n$ operations is at most

the total amortized cost of the $n$ operations.