STAT535代写、python编程设计代写

日期：2022-11-17 10:27

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.