Consider the problem of computing $a$^$n$$,$ where $a $>0$$ and $n$\backslash$in

aturals$$.$

$\{\backslash$bfseries

$\backslash$begin$\{$enumerate$\}$

$\backslash$begin$\{$SLOPPY$\}$

$\backslash$item

State the computational problem $\{$

ormalfont$\backslash$textsc$\{$Exponentiation$\}\}$

in formal Instance$/$Solution form

as is done in the lecture notes.

$\backslash$end$\{$SLOPPY$\}$

$\backslash$item Write CLRS pseudocode for a divide$-$and$-$conquer algorithm for the exponentiation problem of computing $a$^$n$ where $a $>0$$ and $n$ is a positive integer.

$\backslash$item Define and solve a recurrence for the number of multiplications made by your algorithm.

$\backslash$item How does your algorithm compare with a brute$-$force algorithm for this problem?

$\backslash$end$\{$enumerate$\}$

$\}$