Discussion 4:
MT1 Review
Section: 115, CS Scholars
TA: Tammy Nguyen (tammynguyen@berkeley.edu)
* if you didn’t bring a notebook, take 2-3 pieces of blank paper
** also take donuts :-)
Discussion 4:
MT1 Review
Section: 115, CS Scholars
TA: Tammy Nguyen (tammynguyen@berkeley.edu)
* if you didn’t bring a notebook, take 2-3 pieces of blank paper
** also take donuts :-)
Announcements
Concepts to remember
WWPP, print vs return
The following code is loaded in the interpreter. What would the lines on the right output. (Assume they are executed one after another).
Write Error if the code errors or Function if a function object representation is output. Difficulty: Easy
my_print = lambda x: print(x)
weird_print = lambda x: print(x*3)
def non(sense):
if sense and sense + 1:
my_print(sense)
sense, x = sense+2, sense
my_print = weird_print
return print(sense, my_print(x))
>>> print(100)
100
>>> my_print(“nonsense”)
>>> weird_print(my_print)
>>> my_print(weird_print)
>>> weird_print(‘ha’)
>>> non(3)
>>> my_print(non(-1))
WWPP, print vs return
The following code is loaded in the interpreter. What would the lines on the right output. (Assume they are executed one after another).
Write Error if the code errors or Function if a function object representation is output. Difficulty: Easy
my_print = lambda x: print(x)
weird_print = lambda x: print(x*3)
def non(sense):
if sense and sense + 1:
my_print(sense)
sense, x = sense+2, sense
my_print = weird_print
return print(sense, my_print(x))
>>> print(100)
100
>>> my_print(“nonsense”)
>>> weird_print(my_print)
>>> my_print(weird_print)
>>> weird_print(‘ha’)
>>> non(3)
>>> my_print(non(-1))
nonsense
Error
Function
hahaha
3
9
5 None
-3
1 None
None
Environment Diagram, HOF and Lambda
Adapted from Fall 2012 Midterm 1.
Difficulty: hard.
def cheese(sticks):
cheese = sticks
def sticks(cheese):
return 2 * cheese
return cheese(sticks) + sticks(3)
sticks = lambda cheese: cheese(2)
yummy = cheese(sticks)
Solution: here
Recursion, ADT
tree(value, children): creates a tree from with one value and a list of children
value(tree): returns the value in the top node of the tree
children(tree): returns the list of subtrees of the tree
Write a function that takes in a tree of integers and returns True if there is a path from the root to any leaf that sums to n.
def pathToN(t, n):
“””
>>> t = tree(3, [tree(5, [tree(1), tree(2)]), tree(2, [tree(4)])])
>>> pathToN(t, 11)
True
“””
if children(t) == []:
return ___________________
for __________________________:
if _______________________:
return _______________
return False
3
5
2
3
7
4
3 + 5 + 3 = 11
Adapted from Summer 2014 MT1.
Difficulty: Easy.
Recursion, ADT
First step: base case
def pathToN(t, n):
if children(t) == []:
return ___________________
for __________________________:
if _______________________:
return _______________
return False
3
5
2
3
7
4
base case: no children
if value(t) == n, return True, else return False??
pathToN(leaf, 3) == True
pathToN(leaf, 3) == False
Recursion, ADT
First step: base case
def pathToN(t, n):
if children(t) == []:
return ___________________
for __________________________:
if _______________________:
return _______________
return False
3
5
2
3
7
4
base case: no children
pathToN(leaf, 3) == True
pathToN(leaf, 3) == False
return value(t) == n
Recursion, ADT
Second step: recursive call(s)
def pathToN(t, n):
if children(t) == []:
return ___________________
for __________________________:
if _______________________:
return _______________
return False
3
5
2
3
7
4
3 + 5 + 3 = 11
return value(t) == n
pathToN(c1, ?)
pathToN(c2, ?)
each of t’s children c
Recursion, ADT
Second step: recursive call(s)
def pathToN(t, n):
if children(t) == []:
return ___________________
for __________________________:
if _______________________:
return _______________
return False
3
5
2
3
7
4
3 + 5 + 3 = 11
return value(t) == n
so our recursive call is pathToN(c, n-root(t)).
but where does it go?
c in children(t)
pathToN(c2, n-root(t))
pathToN(c1, n-root(t))
Recursion, ADT
Third step: using/combing recursive calls to solve problem
“If a genie gave me the answer to my smaller problems, how could I use them to solve this one?”
def pathToN(t, n):
if children(t) == []:
return ___________________
for __________________________:
if _______________________:
return _______________
return False
3
5
2
3
7
4
3 + 5 + 3 = 11
if there are paths that sum to (n minus the root’s value) starting from any of its children, then return True
return value(t) == n
pathToN(c1, 8)
pathToN(c2, 6)
make recursive call to pathToN(c, n-root(t))?
c in children(t)
or should the recursive call go here?
Recursion, ADT
Third step: using/combing recursive calls to solve problem
“If a genie gave me the answer to my smaller problems, how could I use them to solve this one?”
def pathToN(t, n):
if children(t) == []:
return ___________________
for __________________________:
if _______________________:
return _______________
return False
3
5
2
3
7
4
3 + 5 + 3 = 11
if there are paths that sum to (n minus the root’s value) starting from any of its children, then return True
return value(t) == n
pathToN(c1, 8)
pathToN(c2, 6)
c in children(t)
True
pathToN(c, n-root(t)) == True
Recursion, ADT
Conclusion:
Pass your problems down to your children. They’ll solve them for you! But make sure you account for the case where you don’t have children. Pretty much all tree problems are solved by making your children solve it for you.
def pathToN(t, n):
if children(t) == []:
return ___________________
for __________________________:
if _______________________:
return _______________
return False
3
5
2
3
7
4
3 + 5 + 3 = 11
return value(t) == n
pathToN(c1, 8)
pathToN(c2, 6)
c in children(t)
True
pathToN(c, n-root(t))
Recusion, Linked List ADT
def wheres_waldo(linked_list):
"""
>>> lst = link ("Moe", link ("Larry", link ("Waldo", link ("Curly", empty))))
>>> wheres_waldo(lst)
2
>>> wheres_waldo(link (1 , link (2 , empty)))
’Nowhere’
"""
if ______________________________________________________:
return ‘Nowhere’
elif ____________________________________________________:
return ________________________________________
found_him = wheres_waldo(rest(linked_list))
if ______________________________________________________:
return _________________________________________
return ________________________________________
Adapted from Summer 2014 MT1.
Difficulty: Medium.
Recusion, Linked List ADT
Base case:
def wheres_waldo(linked_list):
if ______________________________________________________:
return ‘Nowhere’
elif ____________________________________________________:
return ________________________________________
found_him = wheres_waldo(rest(linked_list))
if ______________________________________________________:
return _________________________________________
return ________________________________________
empty linked list
if the first element is Waldo
linked_list == empty
first(linked_list) == ‘Waldo’
0
Recusion, Linked List ADT
Recursive call(s):
def wheres_waldo(linked_list):
if ______________________________________________________:
return ‘Nowhere’
elif ____________________________________________________:
return ________________________________________
found_him = wheres_waldo(rest(linked_list))
if ______________________________________________________:
return _________________________________________
return ________________________________________
yes, the rest of the linked list
linked_list == empty
first(linked_list) == ‘Waldo’
0
base case is an empty list or ‘Waldo’ as the first element, so need to keep checking next
Recusion, Linked List ADT
Solve the problem using recursive call:
Given the answer to the rest of our linked list, how can we solve our problem?
def wheres_waldo(linked_list):
if ______________________________________________________:
return ‘Nowhere’
elif ____________________________________________________:
return ________________________________________
found_him = wheres_waldo(rest(linked_list))
if ______________________________________________________:
return _________________________________________
return ________________________________________
either ‘Waldo’ is in the rest of the linked list or he isn’t. recursive call will give us his location in the rest of the list.
linked_list == empty
first(linked_list) == ‘Waldo’
0
he’s somewhere in the rest of the list
whatever index he was at
‘Nowhere’
Recusion, Linked List ADT
Solve the problem using recursive call:
How can we keep track of his location?
def wheres_waldo(linked_list):
if ______________________________________________________:
return ‘Nowhere’
elif ____________________________________________________:
return ________________________________________
found_him = wheres_waldo(rest(linked_list))
if ______________________________________________________:
return _________________________________________
return ________________________________________
if he was the first element, his location is 0 (base case).
otherwise, add 1 to his location given by the recursive call to account for first link.
linked_list == empty
first(linked_list) == ‘Waldo’
0
found_him != ‘Nowhere’
found_him + 1
‘Nowhere’
Recursion with Helper
def deep_apply(lst, n, fn):
"""
>>> numeros = [1, [2, 3], 4, [5, [6, [7, 8]]]]
>>> deep_apply(numeros, 2, lambda x: x*100)
[1, [2, 300], 4, [5, [6, [7, 800]]]]
"""
def helper(lst, counter):
if ___________:
return ___________
first, rest = lst[0], lst[1:]
if type(first) == list:
return _______________________
if ________________:
return _______________________
return _______________________
return helper(________, ________)
Adapted from Summer 2014 MT1.
Difficulty: Hard.
Recursion with Helper
Base case:
What’s the simplest argument?
What should we return?
Should we do computations at this step?
def deep_apply(lst, n, fn):
def helper(lst, counter):
if ___________:
return ___________
first, rest = lst[0], lst[1:]
if type(first) == list:
return _______________________
if ________________:
return _______________________
return _______________________
return helper(________, ________)
lst == []
[]
empty list
nothing to apply fn to, an empty list!
no, no computations to do on an empty list
Recursion with Helper
Recursive calls: can use solution of the rest of the list, increasing counter by 1
Do we recursively call deep_apply or helper?
Can we address deep lists in this step?
def deep_apply(lst, n, fn):
def helper(lst, counter):
if ___________:
return ___________
first, rest = lst[0], lst[1:]
if type(first) == list:
return _______________________
if ________________:
return _______________________
return _______________________
return helper(________, ________)
lst == []
[]
helper so we can increase counter
yes, call helper on the deep list with counter = 1
helper(first, 1)
helper(rest, i+1)
helper(rest, i+1)
Recursion with Helper
Solve problem by black boxing recursive calls:
Since Recursion (our genie) takes care of the rest of the list, we just need to worry about the first.
What should we do if we reach an nth element?
Do we perform computations for deep lists?
def deep_apply(lst, n, fn):
def helper(lst, counter):
if ___________:
return ___________
first, rest = lst[0], lst[1:]
if type(first) == list:
return _______________________
if ________________:
return ____________________________
return ____________________________
return helper(________, ________)
lst == []
[]
no, Recursion handles that completely
helper(first, 1)
helper(rest, i+1)
helper(rest, i+1)
i%n == 0
call fn on it and attach it to the rest of the list
fn(first) +
first +
always keep in mind the return value of your helper function! you cannot add numbers and lists.
Recursion with Helper
Tie up loose ends.
Our outer function always calls the helper with arguments, initializing the parameters.
What should we initialize our parameters to?
def deep_apply(lst, n, fn):
def helper(lst, counter):
if ___________:
return ___________
first, rest = lst[0], lst[1:]
if type(first) == list:
return _______________________
if ________________:
return _______________________________
return ____________________________
return helper(________, ________)
lst == []
[]
lst should be the entire list, counter should start at 1
helper(first, 1)
helper(rest, i+1)
helper(rest, i+1)
i%n == 0
[fn(first)] +
[first] +
lst
1
Study tips
Exam tips
Quiz!
>>> def mid(term):
... def to(night):
... if night[-1] == term:
... return night
... return lambda next: to(night + " " + next)
... return to
>>> exclamation = mid("!")
>>> x = exclamation("The")("midterm")("is tonight")
>>> x("!")
>>> exclamation("Ugh!")("I’m gonna fail.")
>>> f = lambda take: exclamation("I’m")("gonna")(take)("the")("midterm!")
>>> f("ace")
This code is input to the Python interpreter. Fill in what Python would output/print. Write Error if you think the code will error and Function if you think a function object representation will be output.