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

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

  • “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

Recursion, ADT

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

Recursion, ADT

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

Recursion, ADT

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

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:

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

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

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

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

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

For your own practice only.

No attendance this week.

Solution here.

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.

disc4 - Google Slides