Lab 5: Midterm Review

Due at 11:59:59 pm on 03/06/2020.

Starter Files

Download lab05.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

• To receive full credit for this lab, all questions must be attempted.

When you are ready to submit, run ok with the --submit option:

python3 ok --submit

After submitting, ok will display a submission URL, with which you can view your submission on okpy.org.

Review

Question 1: WWPD: Higher Order Functions

Use Ok to test your knowledge with the following "What Would Python Display?" questions:

python3 ok -q hof -u

For all WWPD questions, type Function if you believe the answer is <function...>, Error if it errors, and Nothing if nothing is displayed.

>>> def even(f):
...     def odd(x):
...         if x < 0:
...             return f(-x)
...         return f(x)
...     return odd
>>> steven = lambda x: x
>>> stewart = even(steven)
>>> stewart
______
<function ...>
>>> stewart(61)
______
61
>>> stewart(-4)
______
4

>>> def cake():
...    print('beets')
...    def pie():
...        print('sweets')
...        return 'cake'
...    return pie
>>> chocolate = cake()
______
beets
>>> chocolate
______
Function
>>> chocolate()
______
sweets
'cake'
>>> more_chocolate, more_cake = chocolate(), cake
______
sweets
>>> more_chocolate
______
'cake'
>>> def snake(x, y):
...    if cake == more_cake:
...        return lambda: x + y
...    else:
...        return x + y
>>> snake(10, 20)
______
Function
>>> snake(10, 20)()
______
30
>>> cake = 'cake'
>>> snake(10, 20)
______
30

Question 2: GCD

The greatest common divisor of two positive integers a and b is the largest integer which evenly divides both numbers (with no remainder). Euclid, a Greek mathematician in 300 B.C., realized that the greatest common divisor of a and b is one of the following:

• the smaller value if it evenly divides the larger value (base case), OR
• the greatest common divisor of the smaller value and the remainder of the larger value divided by the smaller value (recursive call)

In other words, if a is greater than b and a is not divisible by b, then

gcd(a, b) == gcd(b, a % b)

Write the gcd function recursively using Euclid's algorithm.

gcd(20, 30) == gcd(20, 30 % 20) == gcd(20, 10) == 10

def gcd(a, b):
    """Returns the greatest common divisor of a and b.
    Should be implemented using recursion.

    >>> gcd(34, 19)
    1
    >>> gcd(39, 91)
    13
    >>> gcd(20, 30)
    10
    >>> gcd(40, 40)
    40
    """
    "*** YOUR CODE HERE ***"
    a, b = max(a, b), min(a, b)
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

Use OK to test your code:

python3 ok -q gcd

This is an example of the elegance that recursive solutions permit. Here for comparison is an iterative solution.

# Iterative solution, if you're curious
def gcd_iter(a, b):
    """Returns the greatest common divisor of a and b, using iteration.

    >>> gcd_iter(34, 19)
    1
    >>> gcd_iter(39, 91)
    13
    >>> gcd_iter(20, 30)
    10
    >>> gcd_iter(40, 40)
    40
    """
    while a % b != 0:
        a, b = b, a % b
    return b

Question 3: Ordered Digits

Implement the function ordered_digits, which takes as input a positive integer and returns True if its digits, read left to right, are in non-decreasing order, and False otherwise. For example, the digits of 5, 11, 127, 1357 are ordered, but not those of 21 or 1375.

Hint: You can use // and % to separate a positive integer into its one's digit and the rest of its digits.

def ordered_digits(x):
    """Return True if the (base 10) digits of X>0 are in non-decreasing
    order, and False otherwise.

    >>> ordered_digits(5)
    True
    >>> ordered_digits(11)
    True
    >>> ordered_digits(127)
    True
    >>> ordered_digits(1357)
    True
    >>> ordered_digits(21)
    False
    >>> result = ordered_digits(1375) # Return, don't print
    >>> result
    False


    >>> cases = [(1, True), (9, True), (10, False), (11, True), (32, False),
    ...          (23, True), (99, True), (111, True), (122, True), (223, True),
    ...          (232, False), (999, True),
    ...          (13334566666889, True), (987654321, False)]
    >>> [ordered_digits(s) == t for s, t in cases].count(False)
    0
    """
    "*** YOUR CODE HERE ***"
    last = x % 10
    val = x // 10
    while x > 0 and last >= x % 10:
        last = x % 10
        x = x // 10
    return x == 0

Use OK to test your code:

python3 ok -q ordered_digits

Question 4: A Bad List Flattener

There is something wrong with the following code! Figure out what is wrong with it, and then fix it to pass the doc string.

Hint, your fix should be very minor! Do not rewrite the whole program.

def bad_list_flattener(lst1, lst2):
    """
    Flattens both lst1 and lst2, and returns the 
    concatenation of the two flattened lists. Flattening 
    a list means to collapse the list into one 
    dimension (like np.flatten).
    >>> girls = [['Rachel', 'Green'], ['Phoebe', 'Buffay']]
    >>> boys = [['Ross', 'Geller'], ['Chandler', 'Bing']]
    >>> bad_list_flattener(girls, boys)
    ['Rachel', 'Green', 'Phoebe', 'Buffay', 'Ross', 'Geller', 'Chandler', 'Bing']
    >>> cats = [['Persian'], ['British', 'Shorthair']]
    >>> dogs = [['Golden', 'Retriever']]
    >>> bad_list_flattener(dogs, cats)
    ['Golden', 'Retriever', 'Persian', 'British', 'Shorthair']
    """
    newlist1 = []
    newlist2 = []
    for inner_lst in lst1:
        for item in inner_lst:
            newlist1 += item
    for inner_lst in lst2:
        for item in inner_lst:
            newlist2 += item
    return newlist1 + newlist2

def bad_list_flattener(lst1, lst2):
    """
    Flattens both lst1 and lst2, and returns the 
    concatenation of the two flattened lists. Flattening 
    a list means to collapse the list into one 
    dimension (like np.flatten).
    >>> girls = [['Rachel', 'Green'], ['Phoebe', 'Buffay']]
    >>> boys = [['Ross', 'Geller'], ['Chandler', 'Bing']]
    >>> bad_list_flattener(girls, boys)
    ['Rachel', 'Green', 'Phoebe', 'Buffay', 'Ross', 'Geller', 'Chandler', 'Bing']
    >>> cats = [['Persian'], ['British', 'Shorthair']]
    >>> dogs = [['Golden', 'Retriever']]
    >>> bad_list_flattener(dogs, cats)
    ['Golden', 'Retriever', 'Persian', 'British', 'Shorthair']
    """
    newlist1 = []
    newlist2 = []
    for inner_lst in lst1:
        for item in inner_lst:
            newlist1 += item
    for inner_lst in lst2:
        for item in inner_lst:
            newlist2 += item
    return newlist1 + newlist2

Use OK to test your code:

python3 ok -q bad_list_flattener

Please note that the question below, flatten, uses tree recursion, which is a topic that will not be tested on the midterm but is in scope for the final.

Question 5: Flatten

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 flatten that takes a (possibly deep) list and "flattens" it. For example:

>>> lst = [1, [[2], 3], 4, [5, 6]]
>>> flatten(lst)
[1, 2, 3, 4, 5, 6]

Hint: you can check if something is a list by using the built-in function isinstance. For example:

>>> isinstance([1,2,3],list)
True
>>> isinstance(3,list)
False

or using the builtin function type.

>>> type([1, 2, 3]) == list
True

def flatten(lst):
    """Returns a flattened version of lst.

    >>> flatten([1, 2, 3])     # normal list
    [1, 2, 3]
    >>> x = [1, [2, 3], 4]      # deep list
    >>> flatten(x)
    [1, 2, 3, 4]
    >>> x = [[1, [1, 1]], 1, [1, 1]] # deep list
    >>> flatten(x)
    [1, 1, 1, 1, 1, 1]
    """
    "*** YOUR CODE HERE ***"
    if not lst:
        return []
    elif type(lst[0]) == list:
        return flatten(lst[0]) + flatten(lst[1:])
    else:
        return [lst[0]] + flatten(lst[1:])

Use OK to test your code:

python3 ok -q flatten

Submit

Make sure to submit this assignment by running:

python3 ok --submit

Extra Credit Practice Open in a new window

These questions are new this semester. They're a mix of Parsons Problems, Code Tracing questions, and Code Writing questions.

Confused about how to use the tool? Check out https://codestyle.herokuapp.com/cs88-lab01 for some problems designed to demonstrate how to solve these types of problems.

These cover some similar material to lab, so can be helpful to further review or try to learn the material. Unlike lab and homework, after you've worked for long enough and tested your code enough times on any of these questions, you'll have the option to view an instructor solution. You'll unlock each question one at a time, either by correctly answering the previous question or by viewing an instructor solution.

Starting from lab 2 onward, each set of questions are worth half (0.5) a point per lab, for a total opportunity of 4-5 points throughout the semester.

Use OK to test your code:

python3 ok -q extra_credit

Past Midterms

For your reference, here is a table of past midterms to study with!