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/lab03a/lab3a.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 = (1, 2, 3) >>> x[0] # Q1 ______ >>> x[3] # Q2 ______ >>> x[-1] # Q3 ______ >>> x[-3] # Q4 ______

>>> x[:2] # Q5 ______ >>> x[1:3] # Q6 ______ >>> x[-2:3] # Q7 ______ >>> x[::2] # Q8 ______ >>> x[::-1] # Q9 ______ >>> x[-1:0:-1] # Q10 ______

>>> y = (1, ) >>> len(y) # Q11 ______ >>> 1 in y # Q12 ______ >>> y + (2, 3) # Q13 ______ >>> (0,) + y # Q14 ______ >>> y * 3 # Q15 ______ >>> z = ((1, 2), (3, 4, 5)) >>> len(z) # Q16 ______

>>> a = (2, 3, 4) >>> for elem in a: # Q17 ... print(elem) ______ >>> for item in a: # Q18 ... print('hi') ______ >>> for elem in range(3) # Q19 ... print(elem) ______

**Problem 1**: For each of the following, give the
correct expression involving x to get 7.

>>> x = (1, 3, 5, 7) >>> x[-1] # example 7 >>> x = (1, 3, (5, 7), 9) >>> _______________ 7 >>> x = ((7,),) >>> _______________ 7 >>> x = (1, (2, (3, (4, (5, (6, (7,))))))) >>> _______________ 7

**Problem 2**: Write a function
reverse which takes a tuple and returns the
reverse. Write both an iterative and a recursive version. You may also
use slicing notation, but don't use
tup[::-1].

def reverse_iter(tup): """ Returns the reverse of the given tuple. >>> reverse_iter((1, 2, 3, 4)) (4, 3, 2, 1) """ "*** YOUR CODE HERE ***" def reverse_recursive(tup): """Returns the reverse of the given tuple. >>> reverse_recursive((1, 2, 3, 4)) (4, 3, 2, 1) """ "*** YOUR CODE HERE ***"

**Problem 3**: Write a function
merge which takes 2 *sorted* tuples
tup1 and tup2,
and returns a new tuple that contains all the elements in the two
tuples in sorted order. Write both a recursive and an iterative
version.

def merge_iter(tup1, tup2): """Merges two sorted tuples. >>> merge_iter((1, 3, 5), (2, 4, 6)) (1, 2, 3, 4, 5, 6) >>> merge_iter((), (2, 4, 6)) (2, 4, 6) >>> merge_iter((1, 2, 3), ()) (1, 2, 3) """ "*** YOUR CODE HERE ***" def merge_recursive(tup1, tup2): """Merges two sorted tuples. >>> merge_recursive((1, 3, 5), (2, 4, 6)) (1, 2, 3, 4, 5, 6) >>> merge_recursive((), (2, 4, 6)) (2, 4, 6) >>> merge_recursive((1, 2, 3), ()) (1, 2, 3) """ "*** YOUR CODE HERE ***"

**Problem 4**: A tuple that contains one or more tuples
as elements is called a *deep*tuple. For example,
(1, (2, 3), 4) is a deep tuple.

Write a function deep_len that takes a tuple 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 tuple by using the
built-in type function. For example,

>>> type(3) == tuple False >>> type((1, 2, 3)) == tuple True

def deep_len(tup): """Returns the deep length of the tuple. >>> deep_len((1, 2, 3)) # normal tuple 3 >>> x = (1, (2, 3), 4) # deep tuple >>> deep_len(x) 4 >>> y = ((1, (1, 1)), 1, (1, 1)) # deep tuple >>> deep_len(y) 6 """ "*** YOUR CODE HERE ***"

One last thing about tuples: they're *immutable* data
structures. This means that once they are created, they can't be
changed. for example, try this:

>>> x = (1, 2, 3) >>> x[0] = 4

This will cause a TypeError complaining
that tuples don't "support item assignment." In other words, you can't
change the elements in a tuple because tuples are immutable. later in
the course, we'll see the opposite -- *mutable* data structures.

Recall that the constructor and selectors for rlists are as follows:

empty_rlist = None def rlist(first, rest=empty_rlist): return (first, rest) def first(rlist): return rlist[0] def rest(rlist): return rlist[1]

As you do the questions below, keep in mind that an rlist is an abstract data type! In other words, your code should not assume that rlists are implemented as tuples.

**Problem 5**: It would be convenient if we had a way to convert from tuples to
rlists. Write a function tup_to_rlist that
does exactly that.

**Hint**: if you are writing the function iteratively, it might
be helpful to reverse the tuple first.

def tup_to_rlist(tup): """Converts a tuple to an rlist. >>> tup = (1, 2, 3, 4) >>> r = tup_to_rlist(tup) >>> first(r) 1 >>> first(rest(rest(r))) 3 >>> r = tup_to_rlist(()) >>> r is empty_rlist True """ "***YOUR CODE HERE ***"

**Problem 6**: Recall the sequence abstraction: a sequence has a finite
**length** and supports **element selection**. Implement the
len_rlist(lst) function, which calculates
the length of an rlist, and the getitem_rlist(i,
lst) function, which gets the *i*th item in the rlist.

def len_rlist(lst): """Returns the length of the rlist. >>> lst = tup_to_rlist((1, 2, 3, 4)) >>> len_rlist(lst) 4 >>> lst = tup_to_rlist(()) >>> len_rlist(lst) 0 """ "*** YOUR CODE HERE ***" def getitem_rlist(i, lst): """Returns the ith item in the rlist. If the index exceeds the length of the rlist, return 'Error'. >>> lst = tup_to_rlist((1, 2, 3, 4)) >>> getitem_rlist(0, lst) 1 >>> getitem_rlist(3, lst) 4 >>> getitem_rlist(4, lst) 'Error' """ "*** YOUR CODE HERE ***"

**Problem 7**: At this point, we want to test your code for any data
abstraction violations. Change the constructors and selectors for
rlists to the following:

empty_rlist = lambda x: x def rlist(first, rest=empty_rlist): return lambda x: first if x == 'hi' else rest def first(lst): return lst('hi') def rest(lst): return lst('lol')

After the changes, try running the doctests again. Do your solutions for Q5 and Q6 still work? If so, you have preserved abstraction!