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

• Project 4 due Friday, 08/05
• 1 EC for final submission by tonight
• Final Review on Friday, 08/05 at 11-12:30 in 2050 VSLB
• Ants composition revisions due Saturday, 08/06
• Scheme recursive art contest due 08/09
• Lab/Discussion next week are optional
• Potluck on 8/10 5-8pm in Wozniak

Concepts to remember

• function call vs function object
• foo() vs foo
• truth-y, false-y values:
• false: 0, None, [], ‘’, etc.
• true: anything else
• execution of if blocks and boolean operators (and, or)
• print vs return
• order of evaluation of assignment statements
• order of evaluation of call expressions
• how to manipulate integers
• how do you get 123 from 1234? 1234//10
• how do you get 4 from 1234? 1234%10
• check if even? n%2 == 0
• list operations
• indexing: 0 based
• slicing: [inclusive:exclusive] makes new lists
• 3 steps to recursion
• base case
• recursive call
• assume correct answer to recursive call and solve problem

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

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

Difficulty: Easy.

First step: base case

• “What are the simplest possible arguments I can get?”
• “Can I find out if the answer is True without doing any work?”
• “Can I find out if the answer is False without doing any work?”

def pathToN(t, n):

if children(t) == []:

return ___________________

for __________________________:

if _______________________:

return _______________

return False

3

5

2

3

7

4

• simplest argument: t is a one node tree, i.e. it has no children.
• yes! if t is only one node, there is a path if its value is n
• yes! if t is only one node, there isn’t a path it its value is not n

base case: no children

if value(t) == n, return True, else return False??

pathToN(leaf, 3) == True

pathToN(leaf, 3) == False

First step: base case

• “What are the simplest possible arguments I can get?”
• “Can I find out if the answer is True without doing any work?”
• “Can I find out if the answer is False without doing any work?”

def pathToN(t, n):

if children(t) == []:

return ___________________

for __________________________:

if _______________________:

return _______________

return False

3

5

2

3

7

4

• simplest argument: t is a one node tree, i.e. it has no children.
• yes! if t is only one node, there is a path if its value is n
• yes! if t is only one node, there isn’t a path it its value is not n

base case: no children

pathToN(leaf, 3) == True

pathToN(leaf, 3) == False

return value(t) == n

Second step: recursive call(s)

• “What are smaller instances of my problem?”
• “How can I reduce my problem size?”

def pathToN(t, n):

if children(t) == []:

return ___________________

for __________________________:

if _______________________:

return _______________

return False

3

5

2

3

7

4

3 + 5 + 3 = 11

• tree design makes this easy; all of t’s children are also trees!

return value(t) == n

pathToN(c1, ?)

pathToN(c2, ?)

each of t’s children c

• we make progress towards n by counting root’s value; new goal is n minus value(root) starting at child nodes

Second step: recursive call(s)

• “What are smaller instances of my problem?”
• “How can I reduce my problem size?”

def pathToN(t, n):

if children(t) == []:

return ___________________

for __________________________:

if _______________________:

return _______________

return False

3

5

2

3

7

4

3 + 5 + 3 = 11

• tree design makes this easy; all of t’s children are also trees!

return value(t) == n

so our recursive call is pathToN(c, n-root(t)).

but where does it go?

• we make progress towards n by counting root’s value; new goal is n minus value(root) starting at child nodes

c in children(t)

pathToN(c2, n-root(t))

pathToN(c1, n-root(t))

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?

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

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

"""

>>> wheres_waldo(lst)

2

’Nowhere’

"""

if ______________________________________________________:

return ‘Nowhere’

elif ____________________________________________________:

return ________________________________________

if ______________________________________________________:

return _________________________________________

return ________________________________________

Difficulty: Medium.

Base case:

• Simplest argument?
• What can I find out without doing any work?

if ______________________________________________________:

return ‘Nowhere’

elif ____________________________________________________:

return ________________________________________

if ______________________________________________________:

return _________________________________________

return ________________________________________

if the first element is Waldo

0

Recursive call(s):

• Is there a smaller instance of my problem?
• How can I approach my base case?

if ______________________________________________________:

return ‘Nowhere’

elif ____________________________________________________:

return ________________________________________

if ______________________________________________________:

return _________________________________________

return ________________________________________

yes, the rest of the linked list

0

base case is an empty list or ‘Waldo’ as the first element, so need to keep checking next

Solve the problem using recursive call:

Given the answer to the rest of our linked list, how can we solve our problem?

if ______________________________________________________:

return ‘Nowhere’

elif ____________________________________________________:

return ________________________________________

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.

0

he’s somewhere in the rest of the list

whatever index he was at

‘Nowhere’

Solve the problem using recursive call:

How can we keep track of his location?

if ______________________________________________________:

return ‘Nowhere’

elif ____________________________________________________:

return ________________________________________

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.

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(________, ________)

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

• do extra problems on hw/labs/discussion sheets
• when stuck on a practice problem for more than 10 minutes, try doing it in your text editor
• allows you to work towards a solution rather than just seeing it
• allows you to see common mistakes you make in your code (off by 1 errors, incorrect control flow, …)
• eat dinner tonight! tummy grumblies are no good for exams

Exam tips

• don’t stay stuck for more than 10 minutes, move on and come back
• as you see in these slides, it’s okay to start out with “pseudocode”
• sometimes we even give points for correct ideas!
• draw diagrams whenever possible!
• double check environment diagrams and WWPP if you’re stuck on other questions
• full credit on ED/WWPP > no/partial credit on code writing q’s

Quiz!

>>> def mid(term):
... def to(night):
... if night[-1] == term:
... return night
... return lambda next: to(night + " " + next)

>>> 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")