$24
Homework 1 Solution
Programming Part (60 Points)
(10 points) The harmonic numbers are the partial sums of the harmonic series. Speci cally, the nth harmonic number is de ned as:
1 1
1
n
1
kX
Hn = 1 + 2 + 3 + + n =
k
=1
(see https://en.wikipedia.org/wiki/Harmonic_number for more de-tails on the harmonic numbers)
Write a short function def harmonic(n) that takes a number n and returns the nth harmonic number.
Now, write the function def harmonicV2(n) that does the same thing as above (returns the nth harmonic number), but using a list comprehension and the built-in sum method.
(10 points) In this problem, we will write two di erent algorithms for nding all the prime numbers up to a given number n.
In each implementation, the algorithm should return a list of all the primes up to (and possibly including) n.
The rst method will use the prime testing algorithm from lecture. You should iterate through all numbers from 1 up to (and possibly including) n. For each number, test if it is prime using the method from class, and if it is, add it to the list of primes. At the end, return the nal list.
Use the third (and most e cient) version of the prime testing algo-rithm, which when testing if a number k is prime only tests factors
p
up to k.
Implement this as a method called find primes(n).
Example: Calling find primes(17) should return the list [2, 3, 5, 7, 11, 13, 17].
1
The second method will implement the Sieve of Eratosthenes. You can read about the Sieve of Eratosthenes at https://en.wikipedia. org/wiki/Sieve_of_Eratosthenes.
The general approach you will use is as follows. Create a list (say, prime lst) of size n + 1, consisting of all True values. When we are nished running the seive algorithm, prime lst[i] will be True if i is prime, and False otherwise.
The seive will work roughly as follows. Start at index i = 2. Then, set prime lst[2*i], prime lst[3*i], prime lst[4*i], etc., to False. Then increment i until prime lst[i] is True, and do the same thing again: set prime lst[2*i], prime lst[3*i], etc., to False. Con-tinue until i reaches the end of the list.
(If this is a bit confusing to you, I recommend reading the Wikipedia page on the Seive of Eratosthenes.)
Once this is done, you will have a list prime lst for which prime lst[i] is True if and only if i is prime. You should then convert this into a single list consisting of the prime numbers. (Try using a list compre-hension for this!)
As an example, when calling prime seive(17), after running the seive portion, prime lst will be True for the indices 2, 3, 5, 7, 11, 13, and 17, and False for all other indices. The function should then construct and return the list [2, 3, 5, 7, 11, 13, 17].
Implement this as: def prime sieve(n).
(10 points) The Leonardo Numbers are a sequence of numbers similar to the Fibonacci numbers. They are de ned as follows:
Ln =
8
1
if n = 1
1
if n = 0
<
Ln 1 + Ln 2 + 1 if n 1
:
So, L0 = L1 = 1, and Ln = Ln 1 + Ln 2 + 1 for n 1.
Write the function: def leonardo(n), which creates a generator, that when iterated over will yield the rst n numbers in the Leonardo sequence (that is, the numbers L0 up to and including Ln 1). For example, the following code:
for val in leonardo(7):
print(val, end= )
should print: 1 1 3 5 9 15 25. Note again that this should be a gener-
ator: do not simply return a list!
(20 points) In this problem, we will modify the dynamic array implemen-tation MyList from class.
2
(a)
Implement the
repr
to return a string representation of the list
in the same format as Python’s built-in list type. For example, if
mylst is a MyList object containing the elements 1,2,3, then calling
str(mylst) should return "[1, 2, 3]".
(b)
Implement the
add
method, so that mylst1 + mylst2 will return
a new MyList object representing the concatenation of the two lists. For example, if mylst1 contains [1, 2, 3] and mylst2 contains [4, 5, 6], then mylst1 + mylst2 should return a new MyList object containing [1, 2, 3, 4, 5, 6].
Note: Your implementation should run in linear time. This means that if mylst1 has n1 elements and mylst2 has n2 elements, com-puting mylst1 + mylst2 should run in time (n1 + n2).
(c) Implement the mul method so that expressions of the form mylst
n, where n is a positive integer, will return a new MyList object that contains n copies of the elements of mylst (this is the same behavior as Python’s built-in list type).
Note: Your implementation should run in linear time, proportional to the length of the new list. This means if mylst has m elements, mylst * n should run in time (m n).
(d) After implementing the mul method, you should notice that syn-tax like mylst * 7 works, returning a new MyList object. However, writing 7 * mylst won’t work. Implement the rmul method so that the syntax 7 * mylst works | it should do the same thing as mylst * 7. See Section 2.3.2 in the textbook for more details about
mul and rmul , and why implementing rmul is necessary to allow writing 7 * mylst.
(10 points) The greatest common divisor (gcd) of two integers a and b is the largest integer that evenly divides both a and b.
Euclid’s Algorithm is a way of nding the greatest common divisor, using the following property: The greatest common divisor of a and b is the same as the greatest common divisor of b and a%b; in symbols, gcd(a; b) = gcd(b; a % b).
Note that the greatest common divisor of any number, a, and 0 is a itself. In symbols: gcd(a; 0) = a.
Write a recursive function: def gcd(a, b), which returns the great-est common divisor of two numbers a and b using Euclid’s algorithm as described above. Note that while it is possible to implement Euclid’s al-gorithm without recursion, in order to get more practice with recursion, you should implement the algorithm using recursion. To be clear: You must use recursion for full credit.
3
Written Part (40 Points)
(10 points) For each of the following code snippets, give the worst-case running time in asymptotic (Big-Oh or Big-Theta) notation. Make sure your answer is tight: For example, if a code snippet runs in time (n4), saying it runs in time O(n5) is technically correct, but it is not tight; you would need to answer (n4) or O(n4) for full credit.
total = 0
for i in range(n):
total += i
for j in range(1,n+1): total += j
total = 0
for i in range(n):
total += i
for j in range(i,n): total += j
total = 0 while n 1:
total += n % 2 n = n // 2
(10 points) Use the de nitions of Big-Oh (O) and Big-Theta ( ) to show the following:
(a)
3n4 + 8n3
3n = (n3)
p
(b)
17n2 + 4n
7 = (n)
(c) Let f(n), g(n), and h(n) be functions. Show that if f(n) = O(g(n))
and g(n) = O(h(n)), then f(n) = O(h(n)).
3. (10 points) In problem 2(a) of the programming part, you implemented a method find primes(n) for nding all primes up to n by using the prime
testing algorithm from class (the third version that tests if k is prime by p
checking for factors up to k).
Analyze the running time of find
primes in asymptotic (Big-Oh) nota-
P
n
p
= p
+ p
+
tion. If necessary, you may use the fact that
k
1
2
+
p
= (np
). Brie y explain your answer.
k=1
n
n
(10 points) Consider the following two approaches for reversing a list:
def reverse1(lst): rev_lst = []
for i in range(len(lst)): rev_lst.insert(0, lst[i])
return rev_lst
4
def reverse2(lst):
rev_lst = []
for i in range(len(lst)-1, -1, -1):
rev_lst.append(lst[i])
return rev_lst
If lst is a list of n integers, what is the worst case running time of reverse1(lst)? Explain your answer.
If lst is a list of n integers, what is the worst case running time of reverse2(lst)? Explain your answer.
5
