By the end of this lab, you should have submitted the lab4
assignment using the command submit lab4.
This lab is due by 11:59pm on 7/8/2014.
Here is a lab04.py starter file for this lab.
Predict what Python will display when you type the following into the interpreter. Then try it to check your answers.
>>> x = [1, 2, 3]
>>> x[0] # Q1
______1
>>> x[3] # Q2
______IndexError
>>> x[-1] # Q3
______3
>>> x[-3] # Q4
______1>>> x = [1, 2, 3, 4]
>>> x[1:3] # Q1
______[2, 3]
>>> x[:2] # Q2
______[1, 2]
>>> x[1:] # Q3
______[2, 3, 4]
>>> x[-2:3] # Q4
______[3]
>>> x[::2] # Q5
______[1, 3]
>>> x[::-1] # Q6
______[4, 3, 2, 1]
>>> x[-1:0:-1] # Q7
______[4, 3, 2]>>> y = [1]
>>> len(y) # Q1
______1
>>> 1 in y # Q2
______True
>>> y + [2, 3] # Q3
______[1, 2, 3]
>>> [0] + y # Q4
______[0, 1]
>>> y * 3 # Q5
______[1, 1, 1]
>>> z = [[1, 2], [3, 4, 5]]
>>> len(z) # Q6
______[2]For each of the following, define the function so the expression evaluates to 7.
>>> x = [1, 3, 5, 7]
>>> def get_seven(lst):
... return lst[-1]
...
>>> get_seven(x) # example
7
>>> x = [1, 3, [5, 7], 9]
>>> get_seven_a(x)
7
>>> x = [[7]]
>>> get_seven_b(x)
7
>>> x = [1, [2, [3, [4, [5, [6, [7]]]]]]]
>>> get_seven_c(x)
7x[2][1]x[0][0]x[1][1][1][1][1][1][0]Write a function reverse that takes a list and returns the reverse.
Write both an iterative and a recursive version. You may use slicing
notation, but don't use list[::-1].
def reverse_iter(lst):
"""Returns the reverse of the given list.
>>> reverse_iter([1, 2, 3, 4])
[4, 3, 2, 1]
"""
"*** YOUR CODE HERE ***"
def reverse_recursive(lst):
"""Returns the reverse of the given list.
>>> reverse_recursive([1, 2, 3, 4])
[4, 3, 2, 1]
"""
"*** YOUR CODE HERE ***"def reverse_iter(lst):
new, i = (), 0
while i < len(lst):
new = (lst[i],) + new
i += 1
return new
def reverse_recursive(lst):
if not lst:
return []
return reverse_recursive(lst[1:]) + (lst[0],)A list that contains one or more lists as elements is called a deep
list. For example, [1, [2, 3], 4] is a deep list.
Write a function deep_len that takes a list and reports its deep
length. See the doctests for the function's behavior. You may write
this function iteratively or recursively.
Hint: you can check if something is a list by using the built-in
type function. For example,
>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True
def deep_len(lst):
"""Returns the deep length of the list.
>>> deep_len([1, 2, 3]) # normal list
3
>>> x = [1, [2, 3], 4] # deep list
>>> deep_len(x)
4
>>> y = [[1, [1, 1]], 1, [1, 1]] # deep list
>>> deep_len(y)
6
"""
"*** YOUR CODE HERE ***"def deep_len(lst):
if not lst:
return 0
elif type(lst[0]) == list:
return deep_len(lst[0]) + deep_len(lst[1:])
else:
return 1 + deep_len(lst[1:])Write a recursive function merge that takes 2 sorted lists lst1
and lst2, and returns a new list that contains all the elements in
the two lists in sorted order.
def merge(lst1, lst2):
"""Merges two sorted lists.
>>> merge([1, 3, 5], [2, 4, 6])
[1, 2, 3, 4, 5, 6]
>>> merge([], [2, 4, 6])
[2, 4, 6]
>>> merge([1, 2, 3], [])
[1, 2, 3]
>>> merge([5, 7], [2, 4, 6])
[2, 4, 5, 6, 7]
"""
"*** YOUR CODE HERE ***"# recursive
def merge(lst1, lst2):
if not lst1 or not lst2:
return lst1 + lst2
elif lst1[0] < lst2[0]:
return (lst1[0],) + merge(lst1[1:], lst2)
else:
return (lst2[0],) + merge(lst1, lst2[1:])
# iterative
def merge(lst1, lst2):
new = ()
while lst1 and lst2:
if lst1[0] < lst2[0]:
new += (lst1[0],)
lst1 = lst1[1:]
else:
new += (lst2[0],)
lst2 = lst2[1:]
if lst1:
return new + lst1
else:
return new + lst2One day, you and a friend decide to work on a programming project — implement a Rational Number interface. Recall that a rational number is any number that can be expressed as p / q, where p and q are integers.
Your friend gets to work implementing an abstract data type (ADT for short) to represent rational numbers. In the meantime, you will be writing functions that perform mathematical operations on rational numbers. You and your friend agree on a set of constructors and selectors:
def make_rat(num, den):
"""Creates a rational number, given a numerator and
denominator.
"""
def num(rat):
"""Extracts the numerator from a rational number."""
def den(rat):
"""Extracts the denominator from a rational number."""make_rat is the constructor, and num and den are the
selectors.
Notice that the functions don't have any bodies yet, so you won't know how they work — but that's okay! As long as you know what each function is supposed to do, you can write your code. This is called data abstraction.
Finish question 8 first. After that, We'll provide you a way to test your code.
Implement addition and subtraction for rational numbers (remember that you can
use your solution for add_rat in sub_rat):
def add_rat(a, b):
"""Adds two rational numbers A and B. For example,
(3 / 4) + (5 / 3) = (29 / 12)
>>> a, b = make_rat(3, 4), make_rat(5, 3)
>>> c = add_rat(a, b)
>>> num(c)
29
>>> den(c)
12
"""
"*** YOUR CODE HERE ***"
def sub_rat(a, b):
"""Subtracts two rational numbers A and B. For example,
(3 / 4) - (5 / 3) = (-11 / 12)
>>> a, b = make_rat(3, 4), make_rat(5, 3)
>>> c = sub_rat(a, b)
>>> num(c)
-11
>>> den(c)
12
"""
"*** YOUR CODE HERE ***"def add_rat(a, b):
new_num = num(a) * den(b) + num(b) * den(a)
new_den = den(a) * den(b)
return make_rat(new_num, new_den)
def sub_rat(a, b):
neg = make_rat(-num(b), den(b))
return add_rat(a, neg)
# alternate solution
def sub_rat(a, b):
new_num = num(a) * den(b) - num(b) * den(a)
new_den = den(a) * den(b)
return make_rat(new_num, new_den)Your friend finally finished implementing the constructors and selectors for the Rational Number ADT — you can use the following code to check your answers to the previous exercises.
def make_rat(num, den):
"""Creates a rational number, given a numerator and denominator."""
return lambda x, y: [lambda: den + x, lambda: num + y]
def num(rat):
"""Extracts the numerator from a rational number."""
return rat(2, 3)[1]() - 3
def den(rat):
"""Extracts the denominator from a rational number."""
return rat(8, 5)[0]() - 8The code your friend wrote will work, but it is very hard to understand (luckily, you respected data abstraction, so your own code doesn't depend on how your friend's works). Not only that, but it doesn't simplify fractions in the constructor!
Consider the following rational:
>>> a = make_rat(6, 9)
>>> num(a)
6
>>> den(a)
9We would like to simplify the rational number so that it becomes (2
/ 3). Write the make_rat function so that it does this, and write the two
selectors num and den to be consistent with your constructor.
Hint: you can write your own Greatest Common Divisor function, or
you can use Python's built-in gcd function.
Also, in make_rat, make sure to add some assert statements to
check that num and den are indeed integers and use appropriate error
messages if they are not (refer to the doctests in the skeleton code).
from fractions import gcd
def make_rat(num, den):
"*** YOUR CODE HERE ***"
def num(rat):
"*** YOUR CODE HERE ***"
def den(rat):
"*** YOUR CODE HERE ***"Anything that is consistent will work here. Here's an example:
def make_rat(num, den):
assert type(num) == int, 'Numerator is not an integer'
assert type(den) == int, 'Denominator is not an integer'
gcd_fraction = gcd(num, den)
return (num // gcd_fraction, den // gcd_fraction)
def num(rat):
return rat[0]
def den(rat):
return rat[1]Now check your solutions again to the previous exercises. Do they still work? If you didn't violate data abstraction, they should!
Now we will fix some data abstraction violations. A data abstraction violation occurs when a piece of code does not use the constructors and selectors of an ADT. Consider the following rational number ADT:
# Constructor
def make_rat(num, dem):
return [num, dem]
# Selectors
def num(rat):
return rat[0]
def dem(rat):
return rat[1]Given that the three functions above are the only constructors and
selectors, the following function print_rat contains two abstraction
violations:
def print_rat(rat):
"""Returns the last element in a vector."""
return print(rat[0], '/', rat[1])The rational number ADT is not guaranteed to be implemented to be a list, so we can't index into 'rat'.
The best way to spot abstraction violations is to ignore the implementation of the constructors and selectors. If you want to take it one step further, you can imagine the constructors and selectors were implemented with lambdas:
# Constructor
def make_rat(num, den):
"""Creates a rational number, given a numerator and denominator."""
return lambda x, y: [lambda: den + x, lambda: num + y]
# Selectors
def num(rat):
"""Extracts the numerator from a rational number."""
return rat(2, 3)[1]() - 3
def den(rat):
"""Extracts the denominator from a rational number."""
return rat(8, 5)[0]() - 8print function above clearly won't work, because it violates
abstraction! How do we fix this? Fix the broken 'print_rat' in your starter
file.
def print_rat(rat):
"""Returns the last element in a vector."""
return print(num(rat), '/', dem(rat))For the following function, spot as many abstraction violations as you can, and rewrite the code to fix it. Use the rational number ADT defined above. This is really important practice, so please make sure you understand why your answers are correct.
def approximate_pi(iter=1000):
""" Computes an approximation of pi based on the idea
pi/4 = (2/3)*(4/3)*(4/5)*(6/5)*(6/7)*(8/7)...
>>> approximate_pi(10)
3.2751010413348074
>>> approximate_pi()
3.1431607055322663
>>> approximate_pi(10000)
3.1417497057380523
"""
result = make_rat(1, 1)
compute_num = lambda x: 2 + 2 * ((x + 1) // 2)
compute_dem = lambda x: 1 + 2 * ((x + 2) // 2)
for i in range(iter):
n = compute_num(i)
d = compute_dem(i)
result = [n * result[0], d * result[1]]
return 4 * num(result) / result[1]def approximate_pi(iter=1000):
""" Computes an approximation of pi based on the idea
pi/4 = (2/3)*(4/3)*(4/5)*(6/5)*(6/7)*(8/7)...
>>> approximate_pi(10)
3.2751010413348074
>>> approximate_pi()
3.1431607055322663
>>> approximate_pi(10000)
3.1417497057380523
"""
result = make_rat(1, 1)
compute_num = lambda x: 2 + 2 * ((x + 1) // 2)
compute_dem = lambda x: 1 + 2 * ((x + 2) // 2)
for i in range(iter):
n = compute_num(i)
d = compute_dem(i)
new_rat = make_rat(n, d)
result = mul_rat(new_rat, result)
return 4 * num(result) / dem(result)