Mathematical Analysis of Recursive Algorithms

ALGORITHM S$($n$)$

$//$Input: A positive integer n

$//$Output: The sum of the first n cubes

if n $=1$ return $1$

else return S$($n $1)+$ n $$ n $$ n

a$.$ Set up and solve a recurrence relation for the number of times the algo$-$

rithm$$s basic operation is executed.

b$.$ How does this algorithm compare with the straightforward nonrecursive

algorithm for computing this sum?

$4.$ Consider the following recursive algorithm.

ALGORITHM Q$($n$)$

$//$Input: A positive integer n

if n $=1$ return $1$

else return Q$($n $1)+2$ n $1$

a$.$ Set up a recurrence relation for this function$$s values and solve it to deter$-$

mine what this algorithm computes.

b$.$ Set up a recurrence relation for the number of multiplications made by this

algorithm and solve it$.$

c$.$ Set up a recurrence relation for the number of additions$/$subtractions made

by this algorithm and solve it$.$

$5.$ Tower of Hanoi

a$.$ In the original version of the Tower of Hanoi puzzle, as it was published in

the $1890$s by $$Edouard Lucas, a French mathematician, the world will end

after $64$ disks have been moved from a mystical Tower of Brahma. Estimate

the number of years it will take if monks could move one disk per minute.

$($Assume that monks do not eat, sleep, or die.$)$

b$.$ How many moves are made by the ith largest disk $(1<=$ i $<=$ n$)$ in this

algorithm?

c$.$ Find a nonrecursive algorithm for the Tower of Hanoi puzzle and imple$-$

ment it in the language of your choice.

$6.$ Restricted Tower of Hanoi Consider the version of the Tower of Hanoi

puzzle in which n disks have to be moved from peg A to peg C using peg

B so that any move should either place a disk on peg B or move a disk from

that peg. $($Of course, the prohibition of placing a larger disk on top of a smaller

one remains in place, too.$)$ Design a recursive algorithm for this problem and

find the number of moves made by it$.$