STAT535: Statistical Computing Fall 2022
Problem Set 6: Computational Complexity
Objective
Collaboration You may work with other students. However, each student must writeup and
hand in their assignment individually. Be sure to indicate whom you worked with in the comments
of your submission.
Readings
Logistics
1. (10 points) Power Function At the start of the semester, you were given a problem set that
asked the following question to test your knowledge of python. The problem set asked you to
compute x raised to the y power. Now, you will implement the algorithm used for computing
the power in an efficient way.
The previous problem set was:
Write a program that does the following in order:
1. Asks the user to enter a number “x”
2. Asks the user to enter a number “y”
3. Prints out number “x”, raised to the power “y”
4. Prints out the log (base 2) of “x”
Use Spyder to create your program, and save your code in a file named ‘ps0.py’. An example
of an interaction with your program is shown below. The words printed in bold are ones the
computer should print, based on your commands, while the words in regular are an example of
a user’s input.
Enter number x: 2
Enter number y: 3
X**y = 8
log(x) = 1
(a) Suppose x = 2 and y = 4. You could compute xy as xy/2 · xy/2. Now, if you called the
function power(x,y), you could compute it as power(x,y) = power(x, y/2)*power(x,y/2).
When you are able to divide a problem into subproblems that themselves look just like
the original with different inputs, what kind of algorithm is used? Draw a tree diagram
of the computations where power(x,y) is at the top; assume y is a power of 2 (Note: it is
the assumption only for part a).
1
2(b) What is the base case (at the leaves of the tree)?
(c) Write a simple recursive formulation of the power function.
(d) Refactor your simple recursive formulation to a memoized dynamic programming formu-
lation.
(e) Refactor your simple recursive formulation to a bottom-up(iterative) dynamic program-
ming formulation.