Lab 8: Midterm 2 Review

Due at 11:59pm on 10/21/2015.

Starter Files

Download lab08.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.

• To receive credit for this lab, you must complete questions 1, 2, and 3 in lab08.py and submit through OK.

Question 1: WWPP: Methods

Use OK to test your knowledge with the following "What Would Python Print?" questions:

python3 ok -q foobar -u

Hint: Remember for all WWPP questions, enter Function if you believe the answer is <function ...> and Error if it errors.

>>> class Foo:
...     def print_one(self):
...         print('foo')
...     def print_two():
...         print('foofoo')
>>> f = Foo()
>>> f.print_one()
______
foo
>>> f.print_two()
______
Error
>>> Foo.print_two()
______
foofoo
>>> class Bar(Foo):
...     def print_one(self):
...         print('bar')
>>> b = Bar()
>>> b.print_one()
______
bar
>>> Bar.print_two()
______
foofoo
>>> Bar.print_one = lambda x: print('new bar')
>>> b.print_one()
______
new bar

Question 2: WWPP: Attributes

Use OK to test your knowledge with the following "What Would Python Print?" questions:

python3 ok -q attributes -u

Hint: Remember for all WWPP questions, enter Function if you believe the answer is <function ...> and Error if it errors.

>>> class Foo:
...     a = 10
...     def __init__(self, a):
...         self.a = a
>>> class Bar(Foo):
...     b = 1
>>> a = Foo(5)
>>> b = Bar(2)
>>> a.a
______
5
>>> b.a
______
2
>>> Foo.a
______
10
>>> Bar.b
______
1
>>> Bar.a
______
10
>>> b.b
______
1
>>> Foo.c = 15
>>> Foo.c
______
15
>>> a.c
______
15
>>> b.c
______
15
>>> Bar.c
______
15
>>> b.b = 3
>>> b.b
______
3
>>> Bar.b
______
1

Question 3: Advanced Counter

Complete the definition of make_advanced_counter_maker, which creates a function that creates counters. These counters can not only update their personal count, but a shared count for all counters. They can also reset either count.

def make_advanced_counter_maker():
    """Makes a function that makes counters that understands the
    messages "count", "global-count", "reset", and "global-reset".
    See the examples below:

    >>> make_counter = make_advanced_counter_maker()
    >>> tom_counter = make_counter()
    >>> tom_counter('count')
    1
    >>> tom_counter('count')
    2
    >>> tom_counter('global-count')
    1
    >>> jon_counter = make_counter()
    >>> jon_counter('global-count')
    2
    >>> jon_counter('count')
    1
    >>> jon_counter('reset')
    >>> jon_counter('count')
    1
    >>> tom_counter('count')
    3
    >>> jon_counter('global-count')
    3
    >>> jon_counter('global-reset')
    >>> tom_counter('global-count')
    1
    """
    "*** YOUR CODE HERE ***"
    global_count = 0
    def make_counter():
        count = 0
        def counter(msg):
            nonlocal global_count, count
            if msg == 'count':
                count += 1
                return count
            elif msg == 'reset':
                count = 0
            elif msg == 'global-count':
                global_count += 1
                return global_count
            elif msg == 'global-reset':
                global_count = 0
        return counter
    return make_counter

Use OK to test your code:

python3 ok -q make_advanced_counter_maker

Question 4: Find Intersection

Implement intersection, which takes two linked lists, xs and ys, and finds the Link at which the two linked list begin to intersect (or overlap). Remember that all Links end with Link.empty, so there will always be some overlap.

For the two linked lists below, z1 should be the start of the linked list that you return. Note that you should be comparing with identity, rather than equality; an intersection means that some part of the Link is shared between xs and ys, not just that they have the same elements.

Try to aim for θ(n) runtime (where n is the sum of the lengths of xs and ys), and even θ(1) additional space.

xs:  x1 -> x2 -> z1 -> z2 -> z3 -> ...
                 ^
                 |
ys:        y1 ---+

def intersection(xs, ys):
    """
    >>> a = Link(1)
    >>> intersection(a, Link.empty) is Link.empty
    True

    >>> b = a
    >>> intersection(a, b).first # intersection begins at a
    1

    >>> looks_like_a = Link(1)
    >>> intersection(a, looks_like_a) is Link.empty # no intersection! (identity vs value)
    True

    >>> b = Link(1, Link(2, Link(3, a)))
    >>> a.first = 5
    >>> intersection(a, b).first # intersection begins at a
    5

    >>> c = Link(3, b)
    >>> intersection(b, c).first # intersection begins at b
    1
    >>> intersection(c, b).first # intersection begins at b
    1

    >>> intersection(a, c).first # intersection begins at a
    5
    """
    "*** YOUR CODE HERE ***"
    if xs is Link.empty or ys is Link.empty:
        return Link.empty

    # make xs and ys the same size
    if len(xs) < len(ys):
        return intersection(xs, ys.rest)
    elif len(xs) > len(ys):
        return intersection(xs.rest, ys)

    # comparison
    while xs is not ys:
        xs, ys = xs.rest, ys.rest
    return xs

Use OK to test your code:

python3 ok -q intersection

Question 5: Trade

In the integer market, each participant has a list of positive integers to trade. When two participants meet, they trade the smallest non-empty prefix of their list of integers. A prefix is a slice that starts at index 0.

Write a function trade that exchanges the first m elements of list first with the first n elements of list second, such that the sums of those elements are equal, and the sum is as small as possible. If no such prefix exists, return the string 'No deal!' and do not change either list. Otherwise change both lists and return 'Deal!'. A partial implementation is provided.

def trade(first, second):
    """Exchange the smallest prefixes of first and second that have equal sum.

    >>> a = [1, 1, 3, 2, 1, 1, 4]
    >>> b = [4, 3, 2, 7]
    >>> trade(a, b) # Trades 1+1+3+2=7 for 4+3=7
    'Deal!'
    >>> a
    [4, 3, 1, 1, 4]
    >>> b
    [1, 1, 3, 2, 2, 7]
    >>> c = [3, 3, 2, 4, 1]
    >>> trade(b, c)
    'No deal!'
    >>> b
    [1, 1, 3, 2, 2, 7]
    >>> c
    [3, 3, 2, 4, 1]
    >>> trade(a, c)
    'Deal!'
    >>> a
    [3, 3, 2, 1, 4]
    >>> b
    [1, 1, 3, 2, 2, 7]
    >>> c
    [4, 3, 1, 4, 1]
    """
    m, n = 1, 1

    "*** YOUR CODE HERE ***"
    equal_prefix = lambda: sum(first[:m]) == sum(second[:n])
    while m < len(first) and n < len(second) and not equal_prefix():
        if sum(first[:m]) < sum(second[:n]):
            m += 1
        else:
            n += 1
    if False: # change this line!
    if equal_prefix():
        first[:m], second[:n] = second[:n], first[:m]
        return 'Deal!'
    else:
        return 'No deal!'

Use OK to test your code:

python3 ok -q trade

Question 6: Boom (Orders of Growth)

What is the order of growth in time for the following function boom? Use big-θ notation.

def boom(n):
    sum = 0
    a, b = 1, 1
    while a <= n*n:
        while b <= n*n:
            sum += (a*b)
            b += 1
        b = 0
        a += 1
    return sum

Use OK to test your code:

python3 ok -q boom -u