CSCl $335$ HW $4$

Name:

ID:

Below are the pseudo codes of $3$ algorithms.

Alg$1($n$)$:

$ifn=0$

else return $1$

end return $2**Alg1(n-1)$

Alg$2($n$)$:

$]=[0$

Alg$3($n$)$:

if $n=0$

return $1$

else

$m=[\frac{n}{2}]$

$p=$Alg$3(m)$

$p=p^{**}p$

if $n$ is odd

else

return $2**p$

return $p$

end

end

a$)$ What does each algorithm compute?

b$)$ What is the running time of each algorithm.

$2.$ Tower of Hanoi is a mathematical puzzle where we have three rods$(rodA,B,C)$ and $n$ disks.

The objective of the puzzle is to move the entire stack from rodA to rodC, obeying the