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)