# Lab 7: Midterm Review lab07.zip

Due by 11:59pm on Friday, July 17.

## Starter Files

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

In order to facilitate midterm studying, solutions to this lab were released with the lab. However, we still encourage you to try out the problems and struggle for a while before looking at the solutions, and submit the lab as usual!

# Required Questions

## Recursion and Tree Recursion

### Q1: Subsequences

A subsequence of a sequence `S` is a sequence of elements from `S`, in the same order they appear in `S`, but possibly with elements missing. Thus, the lists `[]`, `[1, 3]`, `[2]`, and `[1, 2, 3]` are some (but not all) of the subsequences of `[1, 2, 3]`. Write a function that takes a list and returns a list of lists, for which each individual list is a subsequence of the original input.

In order to accomplish this, you might first want to write a function `insert_into_all` that takes an item and a list of lists, adds the item to the beginning of nested list, and returns the resulting list.

``````def insert_into_all(item, nested_list):
"""Assuming that nested_list is a list of lists, return a new list
consisting of all the lists in nested_list, but with item added to
the front of each.

>>> nl = [[], [1, 2], [3]]
>>> insert_into_all(0, nl)
[[0], [0, 1, 2], [0, 3]]
"""
return ______________________________

def subseqs(s):
"""Assuming that S is a list, return a nested list of all subsequences
of S (a list of lists). The subsequences can appear in any order.

>>> seqs = subseqs([1, 2, 3])
>>> sorted(seqs)
[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
>>> subseqs([])
[[]]
"""
if ________________:
________________
else:
________________
________________
``````

Use Ok to test your code:

``python3 ok -q subseqs``

### Q2: Increasing Subsequences

Just like the last question, we want to write a function that takes a list and returns a list of lists, where each individual list is a subsequence of the original input.

This time we have another condition: we only want the subsequences for which consecutive elements are nondecreasing. For example, `[1, 3, 2]` is a subsequence of `[1, 3, 2, 4]`, but since 2 < 3, this subsequence would not be included in our result.

Fill in the blanks to complete the implementation of the `inc_subseqs` function. You may assume that the input list contains no negative elements.

You may use the provided helper function `insert_into_all`, which takes in an `item` and a list of lists and inserts the `item` to the front of each list.

``````def inc_subseqs(s):
"""Assuming that S is a list, return a nested list of all subsequences
of S (a list of lists) for which the elements of the subsequence
are strictly nondecreasing. The subsequences can appear in any order.

>>> seqs = inc_subseqs([1, 3, 2])
>>> sorted(seqs)
[[], [1], [1, 2], [1, 3], [2], [3]]
>>> inc_subseqs([])
[[]]
>>> seqs2 = inc_subseqs([1, 1, 2])
>>> sorted(seqs2)
[[], [1], [1], [1, 1], [1, 1, 2], [1, 2], [1, 2], [2]]
"""
def subseq_helper(s, prev):
if not s:
return ____________________
elif s[0] < prev:
return ____________________
else:
a = ______________________
b = ______________________
return insert_into_all(________, ______________) + ________________
return subseq_helper(____, ____)
``````

Use Ok to test your code:

``python3 ok -q inc_subseqs``

## Mutable Lists

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.

Hint: You can mutate a slice of a list using slice assignment. To do so, specify a slice of the list `[i:j]` on the left-hand side of an assignment statement and another list on the right-hand side of the assignment statement. The operation will replace the entire given slice of the list from `i` inclusive to `j` exclusive with the elements from the given list. The slice and the given list need not be the same length.

``````>>> a = [1, 2, 3, 4, 5, 6]
>>> b = a
>>> a[2:5] = [10, 11, 12, 13]
>>> a
[1, 2, 10, 11, 12, 13, 6]
>>> b
[1, 2, 10, 11, 12, 13, 6]``````

Additionally, recall that the starting and ending indices for a slice can be left out and Python will use a default value. `lst[i:]` is the same as `lst[i:len(lst)]`, and `lst[:j]` is the same as `lst[0:j]`.

``````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]
'Deal!'
>>> a
[4, 3, 1, 1, 4]
>>> b
[1, 1, 3, 2, 2, 7]
>>> c = [3, 3, 2, 4, 1]
'No deal!'
>>> b
[1, 1, 3, 2, 2, 7]
>>> c
[3, 3, 2, 4, 1]
'Deal!'
>>> a
[3, 3, 2, 1, 4]
>>> b
[1, 1, 3, 2, 2, 7]
>>> c
[4, 3, 1, 4, 1]
"""
m, n = 1, 1

equal_prefix = lambda: ______________________
while _______________________________:
if __________________:
m += 1
else:
n += 1

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``

### Q4: Reverse

Write a function that reverses the given list. Be sure to mutate the original list. This is practice, so don't use the built-in `reverse` function!

Hint: You may notice that this problem appears similar to Reverse in Lab 5. However, unlike the implementations in Lab5, this function should NOT return anything. This is to emphasize that this function should utilize mutability.

``````def reverse(lst):
"""Reverses lst using mutation.

>>> original_list = [5, -1, 29, 0]
>>> reverse(original_list)
>>> original_list
[0, 29, -1, 5]
>>> odd_list = [42, 72, -8]
>>> reverse(odd_list)
>>> odd_list
[-8, 72, 42]
"""
``````

Use Ok to test your code:

``python3 ok -q reverse``

## Nonlocal

### Q5: Glookup

Now we will be making our own version of `glookup`, which keeps track of one's current grade out of the assignments completed so far (you can use this to keep track of your points throughout the rest of the semester!)

`glookup` takes in the following dictionary of assignment names mapped to their total point values:

``````cs61a = {
"Homework": 2,
"Lab": 1,
"Exam": 50,
"Final": 80,
"PJ1": 20,
"PJ2": 15,
"PJ3": 25,
"PJ4": 30,
"Extra credit": 0
}``````

`glookup` then returns a function which takes in an assignment keyword and the points earned on that particular assignment. It returns the current grade percentage out of what assignments have been entered so far.

Make sure you read the doctests and understand them fully before you start writing code.

``````cs61a = {
"Homework": 2,
"Lab": 1,
"Exam": 50,
"Final": 80,
"PJ1": 20,
"PJ2": 15,
"PJ3": 25,
"PJ4": 30,
"Extra credit": 0
}

def make_glookup(class_assignments):
""" Returns a function which calculates and returns the current
grade out of what assignments have been entered so far.

>>> student1 = make_glookup(cs61a) # cs61a is the above dictionary
>>> student1("Homework", 1.5)
0.75
>>> student1("Lab", 1)
0.8333333333333334
>>> student1("PJ1", 18)
0.8913043478260869
"""
``````

Use Ok to test your code:

``python3 ok -q make_glookup``

## Submit

Make sure to submit this assignment by running:

``python3 ok --submit``

# Suggested Questions

## Recursion / Tree Recursion

### Q6: Number of Trees

How many different possible full binary tree (each node has 2 branches or 0, but never 1) structures exist that have exactly n leaves?

For those interested in combinatorics, this problem does have a closed form solution):

``````def num_trees(n):
"""How many full binary trees have exactly n leaves? E.g.,

1   2        3       3    ...
*   *        *       *
/ \      / \     / \
*   *    *   *   *   *
/ \         / \
*   *       *   *

>>> num_trees(1)
1
>>> num_trees(2)
1
>>> num_trees(3)
2
>>> num_trees(8)
429

"""
if ____________________:
return _______________
return _______________
``````

Use Ok to test your code:

``python3 ok -q num_trees``

## Nonlocal

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 also 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:

>>> 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
"""
________________
def ____________(__________):
________________
def ____________(__________):
________________
``python3 ok -q make_advanced_counter_maker``