Homework 1 Data Types, Functions and Conditionals Solution

Read this rst. A few things to bring to your attention:




Start early! If you run into trouble installing things or importing packages, it’s best to nd those problems well in advance, not the night before your assignment is due when we cannot help you!



Make sure you back up your work! I recommend, at a minimum, doing your work in a Dropbox folder or, better yet, using git, which is well worth your time and e ort to learn.



Instructions on writing and submitting your homework.




Failure to follow these instructions will result in lost points. Your homework should be written in a jupyter notebook le. I have made a template available on Canvas, and on the course website at http://www-personal.umich.edu/~klevin/teaching/ Winter2019/STATS507/hw_template.ipynb. You will submit, via Canvas, a .zip le called yourUniqueName_hwX.zip, where X is the homework number. So, if I were to hand in a le for this, homework 1, it would be called klevin_hw1.zip. Contact the instructor or your GSI if you have trouble creating such a le.




When I extract your compressed le, the result should be a directory, also called yourUniqueName_hwX. In that directory, at a minimum, should be a jupyter notebook le, called yourUniqueName.hwX.ipynb, where again X is the number of the current homework. You should feel free to de ne supplementary functions in other Python scripts, which you should include in your compressed directory. So, for example, if the code in your notebook le imports a function from a Python le called supplementary.py, then the le supplementary.py should be included in your submission. In short, I should be able to extract your archived le and run your notebook le on my own machine. Please include all of your code for all problems in the homework in a single Python notebook unless instructed otherwise, and please include in your notebook le a list of any and all people with whom you discussed this homework assignment. Please also include an estimate of how many hours you spent on each of the sections of this homework assignment.




These instructions can also be found on the course web page at http://www-personal. umich.edu/~klevin/teaching/Winter2019/STATS507/hw_instructions.html. Please direct any questions to either the instructor or your GSI.




Warm up: De ning Simple Functions (2 points)



In this problem, you will get practice de ning simple functions in Python.


STATS507: Data Analysis in Python
2






De ne a function called say_hi, which takes no arguments and prints the string Hello, world! when called.



De ne a function called goat_pad, which takes a string as its only argument, and prints that string, prepended and appended with the string goat. So, goat_pad(’bird’)



should produce the output

goatbirdgoat




goat_pad(’_’) should produce the output




goat_goat




and so on. You may assume that the input is a string, so there is no need to perform any error checking in your function.




De ne a function called print_n, which takes two arguments, a string s and an integer n (in that order), and prints the string n times, each on a separate line. You may assume that s is a string and that the integer n is non-negative.



Euclid’s algorithm (2 points)



Euclid’s algorithm (https://en.wikipedia.org/wiki/Euclidean_algorithm) is a method for nding the greatest common divisor (GCD) of two numbers. Recall that the GCD of two numbers m and n is the largest number that divides both m and n.




The Wikipedia page above includes several pseudocode implementations of Euclid’s algorithm. Choose one of these, and use it to implement a function gcd, which takes two integers as its arguments and returns their GCD. You may assume that both inputs are integers, so there is no need to include any error checking in your function. Note: this is one of the rare occasions where you have my explicit permission to look up your answer. Unless otherwise stated (e.g., as in this problem), looking up solutions on Wikipedia or in any other non-class resource will be considered cheating!



Use your function to evaluate the GCDs of the following pairs of numbers:



2018, 2019



1200, 300



5040, 60



What does your function do if one or both of its arguments are negative? Does this behavior make sense?



Approximating Euler’s number e (3 points)



The base of the natural logarithm, e, is typically de ned as the in nite sum




1
1
1
1
1




Xk






















e =
k!
=1+1+


+




+


+:::;
(1)
=0
2
6
24



























where k! denotes the factorial of k,




k! = k (k 1) (k 2) 3 2 1;

STATS507: Data Analysis in Python
3






where we de ne 0! = 1 by convention. For more on Euler’s number, see https://en. wikipedia.org/wiki/E_(mathematical_constant). In this problem, we will explore di erent approaches to approximating this number.




1. An early characterization of Euler’s number, due to Jacob Bernoulli, was as the limit

of










1


x
1 +


(2)
x
as x ! 1. De ne a function called euler_limit that takes as an argument an integer n, and returns a oat that approximates e by taking x = n in Equation (2). You may assume that the input to your function will be a positive integer.




De ne a function called euler_infinite_sum that takes a single non-negative in-teger argument n, and returns an approximation to e based on the rst n terms of the sum in Equation (1). Your function should return a oat. You may assume that the input will be a non-negative integer, so you do not need to include error check-ing in your function. As an example, euler_infinite_sum(4) should return the sum of the rst four terms in Equation 1, so that euler_infinite_sum(4) returns



1 + 1 + 1=2 + 1=6 2:667. Note: the sum in Equation 1 starts counting with k = 0 (i.e., it is \0-indexed"), while our function starts counting with n = 1 (i.e., it is \1-indexed"). euler_infinite_sum(1) should use one term from Equation (1), so that euler_infinite_sum(1) returns 1. Similarly, euler_infinite_sum(0) should return 0, since by convention an empty sum is equal to zero.




De ne a function called euler_approx that takes a single argument, a oat epsilon, and uses the sum in (1) to obtain an approximation of e that is within epsilon of the true value of e. Hint: use a while-loop. Note: you can use the Python math module to get the true value of e (up to oating point accuracy): math.exp(1).



De ne a function called print_euler_sum_table that takes a single positive integer



n as an argument and prints the successive values obtained from euler_infinite_sum(k) as k ranges from 1 to n, one per line.




Which of these two approximations is better?



Testing Properties of an Integer (3 points)



In this problem, you’ll get a bit more practice working with conditionals, and a rst exposure to the kind of thinking that is required in a typical \coding interview" question. A positive integer n is a power of 2 if n = 2p for some integer p 0.




Write a function is_power_of_2 that takes a positive integer as its only argument and returns a Boolean indicating whether or not the input is a power of 2. You may assume that the input is a positive integer. You may not use the built-in math.sqrt function in your solution. You should need only the division and modulus (%) operations. Hint: the simplest solution to this problem makes use of recursion, though recursion is not necessary.



Generalize your previous solution to a function is_power that takes two positive inte-gers as its arguments, b and n, in that order, and returns a Boolean. is_power(b,n) should return True if n is a power of b and False otherwise.