Introduction to Algorithms

Question 1

Iterative

Answer 1

Iterative (“bottom-up”): A loop structure builds up to a solution.

SUMSQUARESITERATIVE(𝑛𝑛)
𝑠𝑠𝑠𝑠𝑠𝑠= 0
for𝑖𝑖=1to 𝑛𝑛
𝑠𝑠𝑠𝑠𝑠𝑠=𝑠𝑠𝑠𝑠𝑠𝑠+𝑖𝑖2
return 𝑠𝑠𝑠𝑠𝑠𝑠

Question 2

Recursive

Answer 2

Recursive (“top-down”): The algorithm calls itself on smaller instances of the same problem.

SUMSQUARESRECURSIVE(𝑛𝑛)
if 𝑛𝑛==1
return 1
else
return SUMSQUARESRECURSIVE𝑛𝑛−1+𝑛𝑛2