We've provided you with a starter file that contains the code you will be using throughout this lab. You can get it by logging onto your class account and running the command:
cp ~cs61a/lib/lab/lab02b/lab2b.py .
Don't forget the dot at the end!
Once you copy the file to your own account, you can open it up in your favorite text editor or Emacs, instead of typing all your code directly into the Python interpreter. This way, you can save your progress and quickly revise code.
Try to figure out what Python will display after the following lines are entered. Then type them into the interpreter to check your answers.
>>> x = (4 + 5, 9 // 2) >>> x # Q1 ______ >>> x[0] # Q2 ______ >>> x[1] # Q3 ______ >>> x[2] # Q4 ______ >>> len(x) # Q5 ______ >>> y = (1,) >>> z = (x, y) >>> z # Q6 ______ >>> z[0] # Q7 ______ >>> z[0][0] # Q8 ______ >>> z[1][0] # Q9 ______ >>> len(z) # Q10 ______ >>> x + y # Q11 ______ >>> len(x + y) # Q12 ______ >>> (8, 3)[0] # Q13 ______
One 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 questions 1 through 4 first. We'll then provide you a way to test your code
Problem 1: Implement addition and subtraction for rational numbers:
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 ***"
Problem 2: Similarly, implement multiplication and division for rational numbers:
def mul_rat(a, b):
"""Multiplies two rational numbers A and B. For example,
(3 / 4) * (5 / 3) = (15 / 12)
>>> a, b = make_rat(3, 4), make_rat(5, 3)
>>> c = mul_rat(a, b)
>>> num(c)
15
>>> den(c)
12
"""
"*** YOUR CODE HERE ***"
def div_rat(a, b):
"""Divides two rational numbers A and B. Keep in mind that A / B
is equivalent to A * (1 / B). For example,
(3 / 4) / (5 / 3) = (9 / 20)
>>> a, b = make_rat(3, 4), make_rat(5, 2)
>>> c = div_rat(a, b)
>>> num(c)
9
>>> den(c)
20
"""
"*** YOUR CODE HERE ***"
Problem 3: Implement a function eq_rat, which checks if two rational numbers are equal. This isn't as straightforward as it seems; for example, (2 / 3) is equal to (6 / 9).
def eq_rat(a, b):
"""Returns True if two rational numbers A and B are equal. For
example, (2 / 3) = (6 / 9), so eq_rat would return True.
>>> a, b = make_rat(2, 3), make_rat(6, 9)
>>> eq_rat(a, b)
True
>>> c, d = make_rat(1, 4), make_rat(1, 2)
>>> eq_rat(c, d)
False
"""
"*** YOUR CODE HERE ***"
Problem 4: Finally, implement an approximation of the irrational number e (approximately 2.718). We can represent e as an infinite series of rational numbers:
where the ! symbol denotes factorial. The function approx_e should approximate e to a specified number of terms in the series described above (the 0th term is 1 / 0!). You should return the answer as a rational number object.
Hint: you can use the functions you defined above.
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
def approx_e(terms=100):
"""Approximates e to the specified number of TERMS.
>>> num(approx_e(0))
1
>>> num(approx_e(1))
2
>>> result = approx_e(2)
>>> num(result)
5
>>> den(result)
2
"""
"*** YOUR CODE HERE ***"
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 Exercise 2.
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]() - 8
Problem 5: the 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). Help your friend write a more readable set of constructors and selectors.
Also, in make_rat, make sure to add some assert statements to check that num and den are indeed integers.
def make_rat(num, den):
"*** YOUR CODE HERE ***"
def num(rat):
"*** YOUR CODE HERE ***"
def den(rat):
"*** YOUR CODE HERE ***"
Now check your solutions again to Exercise 2. Do they still work? If you didn't violate data abstraction, they should!
Problem 6: there's an improvement that could be made to the constructor, make_rat. For example, consider the following rational:
>>> a = make_rat(6, 9) >>> num(a) 6 >>> den(a) 9
We would like to simplify the rational number so that it becomes (2 / 3). Rewrite the make_rat function so that it does this. Don't forget that the numerator and denominator should still be integers!
Hint: you can write your own Greatest Common Divisor function, or you can use Python's built-in gcd function.
from fractions import gcd
def make_rat(num, den):
"*** YOUR CODE HERE ***"
Again, your code from Exercise 2 should still work, even after these changes.
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 vector ADT:
# constructor
def make_vector(*elements):
"""Creates an arbitrarily long vector."""
return elements
# selectors
def get_length(vector):
"""Returns the length of the vector, i.e. the number of elements
in the vector."""
return len(vector)
def get_elem(vector, i):
"""Returns the ith element in the vector."""
return vector[i]
Given that the three functions above are the only constructors and selectors, the following function last contains two abstraction violations:
def last(vector):
"""Returns the last element in a vector."""
length = len(vector)
return vector[length - 1]
The first violation is len(vector). The Vector ADT is not guaranteed to be implemented as a tuple, or even a Python sequence, so we can't use the built-in len function, which only works on Python sequences.
The second violation is vector[length - 1]. Even if we correctly get the length, we can't just index (use square brackets notation with) the Vector as if it were a tuple -- we aren't guaranteed that it'll be implemented as a tuple.
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_vector(*elements):
"""Creates an arbitrarily long vector."""
return lambda: elements
# selectors
def get_length(vector):
"""Returns the length of the vector, i.e. the number of elements
in the vector."""
return len(vector())
def get_elem(vector, i):
"""Returns the ith element in the vector."""
return vector()[i]
Now, the last function above clearly won't work, because it violates abstraction!
Problem 7: For the following functions, spot as many abstraction violations as you can, and rewrite the code to fix it. Use the Vector ADT defined above.
def dot(a, b):
"""Returns the dot product of two Vectors A and B."""
assert len(a) == len(b), "Vectors aren't aligned"
i, product = 0, 0
while i < len(a):
product += a[i] * b[i]
return product
def largest_elem(a):
"""Returns the largest element in the Vector A."""
return max(a)