Lab 7: Midterm Review
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 subseqsQ2: 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_subseqsMutable Lists
Q3: 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.
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 fromiinclusive tojexclusive 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 aslst[i:len(lst)], andlst[:j]is the same aslst[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]
>>> 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
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 tradeQ4: 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]
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q reverseNonlocal
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
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q make_glookupSubmit
Make sure to submit this assignment by running:
python3 ok --submitSuggested 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_treesNonlocal
Q7: 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 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:
>>> 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
"""
________________
def ____________(__________):
________________
def ____________(__________):
________________
"*** YOUR CODE HERE ***"
# as many lines as you want
________________
________________
Use Ok to test your code:
python3 ok -q make_advanced_counter_maker