This notebook shows solutions to homework 4 for Stats507
In this exercise, you’ll get some practice working with iterators and generators. Note: in this problem, the word enumerate is meant in the sense of returning elements, not in the sense of the Python function enumerate
. So, if I say that an iterator enumerates a sequence $a_0,a_1,a_2,\dots,$ I mean that these are the elements that it returns upon calls to the __next__
method, not that it returns pairs $(i,a_i)$ like the enumerate
function.
Fibo
of iterators that enumerate the Fibonacci numbers. For the purposes of this problem, the Fibonacci sequence begins $0,1,1,2,3,\dots,$ with the $n$-th Fibonacci number $F_n$ given by the recursive formula $F_n = F_{n−1} + F_{n−2}$. Your solution should not make use of any function aside from addition (i.e., you should not need to use the function fibo()
defined in lecture a few weeks ago). Your class should support, at a minimum, an initialization method, a __iter__
method (so that we can get an iterator) and a __next__
method. Note: there is an especially simple solution to this problem that can be expressed in just a few lines using tuple assignment.class Fibo:
def __init__(self):
self.f_n2 = 0
self.f_n1 = 1
def __next__(self):
self.fibNum = self.f_n2
self.f_n = self.f_n1 + self.f_n2
(self.f_n1, self.f_n2) = (self.f_n, self.f_n1)
return(self.fibNum)
def __iter__(self):
return(self)
# f = Fibo()
# print([next(f) for _ in range(12)])
GenFibo
of iterators that enumerate generalized Fibonacci numbers. Your class should inherit from the Fibo
class defined in the previous subproblem. The initialization method for the GenFibo
class should take two optional arguments that specify the values of $F_0$ and $F_1$, in that order, and their values should default so that F = GenFibo()
results in an enumerator equivalent to the one that would have been created if you had called F = Fibo()
(i.e., GenFibo()
should produce an iterator over the Fibonacci numbers).class GenFibo(Fibo):
def __init__(self, f_n2 = 0, f_n1 = 1):
self.f_n2 = f_n2
self.f_n1 = f_n1
# g = GenFibo(2, 1)
# [next(g) for _ in range(12)]
primes
that enumerates the prime numbers. Recall that a prime number is any integer $p > 1$ whose only divisors are $p$ and 1. Note: you may use the function is_prime
that we defined in class (or something similar to it), but such solutions will not receive full credit, as there is a more graceful solution that avoids declaring a separate function or method for directly checking primality. Hint: consider a pattern similar to the one seen in lecture using the any
and/or all
functions.def primes():
(primesList, num) = ([], 2)
while(True):
while(any(num % x == 0 for x in primesList)):
num += 1
primesList.append(num)
yield num
# p = primes()
# [next(p) for _ in range(12)]
ulam
that enumerates the Ulam numbers. Hint: it will be helpful to try and break this problem into smaller, simpler subproblems. In particular, you may find it helpful to write a function that takes a list of integers t
and one additional integer u
, and determines whether or not u
is expressible as a sum of two distinct elements of t
in exactly one way.def updateUlamNums(ulamNums, sumSet, index):
currentNum = ulamNums[index]
i = 0
while i < index:
# Initialize new number to insert
newNum = currentNum + ulamNums[i]
# Check if we have already seen this newNum and add it to our
# Sums Set if we haven't seen it
if (newNum not in sumSet):
sumSet.add(newNum)
# Insert the newNum in a sorted way from the tail of our Ulam Nums list
j = len(ulamNums) - 1
while newNum < ulamNums[j]:
j -=1
ulamNums.insert(j + 1, newNum)
# Otherwise remove the newNum from our Ulam Nums List
elif newNum in ulamNums[index + 1:]:
ulamNums.remove(newNum)
i += 1
def ulam():
(ulamNums, sumSet, index) = ([1, 2], {1, 2}, 1)
while(True):
updateUlamNums(ulamNums, sumSet, index)
yield ulamNums[index - 1]
index += 1
# u = ulam()
# [next(u) for _ in range(20)]
In this exercise you’ll write a few simple list comprehensions and generator expressions. Again in this problem I use the term enumerate to mean that a list comprehension or generator expression returns certain elements, rather than in the sense of the Python function enumerate
.
pow2minus1
.pow2minus1 = [2**(n) - 1 for n in range(1,21)]
caterer
. Hint: you may find it useful to define a generator that enumerates the non-negative integers.def nonNegNums():
n = -1
while True:
n += 1
yield n
n = nonNegNums()
caterer = ((i**2 + i + 2) // 2 for i in n)
For ease of grading, please assign this generator expression to a variable called tetra
. Hint: you may find it useful to define a generator that enumerates the positive integers.
import scipy.special
def positiveIntegers():
z = 0
while True:
z += 1
yield z
pos = positiveIntegers()
tetra = (int(scipy.special.binom(i + 2, 3)) for i in pos)
In this exercise, you’ll learn a bit about map, filter and reduce operations. We will revisit these operations in a few weeks when we discuss MapReduce and related frameworks in distributed computing. In this problem, I expect that you will use only the functions map
, filter
and functions from the functools
and itertools
modules, along with the range
function (and similar list-related functions) and a sprinkling of lambda expressions.
sum_of_even_squares
.import functools, itertools
sum_of_even_squares = functools.reduce(lambda x,y: x + y, map(lambda x: x**2, (2*i for i in range(1, 11))))
primes
generator that you defined above. For ease of grading, please assign the output of this expression to a variable called product_of_primes
.p = primes()
product_of_primes = functools.reduce(lambda x,y: x * y, (next(p) for _ in range(13)))
primes
generator that you defined above. For ease of grading, please assign the output of this expression to a variable called squared_primes
.p = primes()
squared_primes = functools.reduce(lambda x,y: x + y, map(lambda x: x**2, (next(p) for _ in range(31))))
harmonics
.harmonics = list(itertools.accumulate(range(1, 21), lambda x,y: x + (1 / y)))
tetra_geom
.pos = positiveIntegers()
t = (int(scipy.special.binom(i + 2, 3)) for i in pos)
tetra_geom = functools.reduce(lambda x,y: x * y, (next(t) for _ in range(12)))**(1 / 12)
In this exercise you’ll get a bit of experience writing higher-order functions. You may ignore error checking in this problem.
make_poly
that takes a list of numbers (ints and/or floats) coeffs
as its only argument and returns a function p
. The list coeffs
encodes the coefficients of a polynomial, $p(x) = a_0 + a_1x + a_2x^2 + \dotsm + a_nx^n$, with $a_i$ given by coeffs[i]
. The function p
should take a single number (int or float) x
as its argument, and return the value of the polynomial $p$ evaluated at x
.def make_poly(coeffs):
def p(x):
return sum(coeffs[i] * (x**i) for i in range(len(coeffs)))
return p
# coeffs = [1, 2, 3]
# p = make_poly(coeffs)
eval_poly
that takes two lists of numbers (ints and/or floats), coeffs
and args
. coeffs
encodes the coefficients of polynomial $p$, and your function should return the list of numbers (ints and/or floats) representing the result of evaluating the polynomial $p$ on each of the elements in args
, in order. You should be able to express the solution to this problem in a single line (not including the function definition header, of course). Your function should make use of make_poly
from the previous part to receive full credit.def eval_poly(coeffs, args):
return list(map(make_poly(coeffs), args))
# args = [1, 2, 3]
# eval_poly(coeffs, args)