1. (8.0 points) What Would Python Display?

For each part of this question, you will be shown code that is executed in the Python interpreter, and you should write what is printed to the interpreter after executing the last line.

● If a StopIteration exception occurs as a result of executing a line, you should write StopIteration

● If an iterator object is displayed as the result of executing a line, you should write Iterator, unless that object is a generator. If a generator object is displayed as the result of executing a line, you should write Generator

● If an error arises as a result of executing a line that is not a StopIteration, you should write Error

● If nothing is displayed as the result of executing a line, you should write Nothing

You should assume that each part is executed in order—that all the code from the previous parts have been executed before the next part.

(a) (1.0 pt)

>>>  a  =  [1,  2,  3,  5,  8,  13]

>>>  i  =  iter(a)

>>>  j  =  iter(a)

>>>  next(i)  +  next(j)

(2.0 pt)

>>>  next(i)  +  next(i)

(c) (2.0 pt)

>>>  def mystery(n):

. . .          i  =  1

. . .         while  i  < n:

. . .                  if  n  %  i  ==  0:

. . .                         yield  i

. . .                  i  +=  1

...

>>> m  = mystery(8)

>>> m

(3.0 pt)

>>>  for  x  in  range(10):

. . .         print(next(m))

...

2. (10.0 points) Lambdistinction

Fill in the blanks of the environment diagram corresponding to executing the following code block.

1 |  j  =  lambda  j:  not  j

2 |  def  g(i,  p):

3 |          j  =  lambda  i:  p(i  -  1)

4 |          def  h(k):

5 |                 return  j(k(i  +  2)  -  1)

6 |          return  h

7 |

8 |  p  =  lambda  p:  not  p

9 |  r  =  g(-4,  p)(lambda  r:  r  *  -1)

(a) (1.0 pt) Fill in blank (a)

(b) (1.0 pt) Fill in blank (b)

(c) (2.0 pt) Fill in blank (c)

(d) (1.0 pt) Fill in blank (d)

(e) (2.0 pt) Fill in blank (e)

(2.0 pt) Fill in blank (f)

(1.0 pt) Fill in blank (g)

3. (15.0 points) Pruning and Sprouting (a) (8.0 points) Prune Below

Fill in the definition of the function prune_below,  which takes in one  argument  t,  that is  a Tree. prune_below also takes in a second optional parameter, seen_before, which is a list containing all of the values the function has seen in t’s parent.

prune_below mutates t by removing all subtrees whose labels are equal to t .label, and then mutates all remaining subtrees of t by the same process.

def  prune_below(t,  seen_before=[]):

"""

>>>  t  =  Tree(5,  [Tree(4,  [Tree(3),  Tree(4),  Tree(5)]),  Tree(5,  [Tree(6),  Tree(7)])]) >>>  print(t)

5

4

3

4

5

5

6

7

>>>  prune_below(t)

>>>  print(t)

5

4

3

"""

seen_before  =  __________

(a)

new_branches  =  [b  for  b  in  t .branches  if  __________]

(b)

__________

(c)

for  b  in  t .branches:

__________

(d)

i. (2.0 pt) Fill in blank (a)

o seen_before .append(t .label)

o seen_before[1:]

● seen_before  +  [t .label]

o [t .label]

o Tree(t .label)

o list(seen_before)

o seen_before  +  t .label

o seen_before  +  [b .label  for  b  in  t .branches]

o seen_before .extend([b .label  for  b  in  t .branches])

o seen_before  +=  [t .label]

ii. (3.0 pt) Fill in blank (b)

b .label not in seen_before

iii. (2.0 pt) Fill in blank (c)

o t .branches .extend(new_branches)

o t .branches  =  [b .label  for  b  in  t .branches]

o return  Tree(t .label,  new_branches)

o t .branches .remove(new_branches)

o prune_below(t,  new_branches)

o t  =  Tree(t .label,  new_branches)

o new_branches .remove(t .label)

● t .branches  =  new_branches

iv. (1.0 pt) Fill in blank (d)

prune_below(b, seen_before)

(b) (7.0 points) Sprout Tree

In this problem, we’ll write a function that “sprouts” new trees from a given root, which can be any integer. We’ll also use a function sprouter, that takes in a single integer as an argument and returns a list. To sprout a new tree, we need to construct an instance of the Tree class whose label is root. We then call

sprouter on root to get a list of numbers that will serve as the labels of our tree’s branches.                   Depending on how deep we want our tree to be, we can repeat the process on the labels of each of our new branches, using the same sprouter function.

For example, the below diagram illustrates how to sprout a tree with a root of 3 and a sprouter function of lambda  x:  [x  -  1,  x  +  1].

Fill in the definition of sprout_tree below, which takes in three parameters: root, sprouter, and d, and returns a new tree of depth d that is sprouted from root by applying the sprouter function. You can assume that d will always be >=  0.

def  sprout_tree(root,  sprouter,  d):

"""

>>> minus_plus_one  =  lambda  x:  [x  -  1,  x  +  1]

>>>  print(sprout_tree(3, minus_plus_one,  0))

3

>>>  print(sprout_tree(3, minus_plus_one,  1))

3

2

4

>>>  print(sprout_tree(3, minus_plus_one,  2))

3

2

1

3

4

3

5

"""

if  __________ :

(a)

return  __________

(b)

new_branches  =  [__________  for  i  in  __________]

(c)                                  (d)

return  __________

(e)

i. (1.0 pt) Fill in blank (a)

d == 0

ii. (1.0 pt) Fill in blank (b)

Tree(root)

iii. (2.0 pt) Fill in blank (c)

iv.

.

sprout_tree(i, sprouter, d -  1)

(2.0 pt) Fill in blank (d)

sprouter(root)

(1.0 pt) Fill in blank (e)

Tree(root, new_branches)

4. (15.0 points) Linked List Comprehension

In Python, we can use list comprehensions to quickly generate lists from other lists—list comprehensions include an expression that is applied to each element in the list, and can optionally include an if clause.

>>>  a  =  [1,  2,  3,  4,  5]

>>>  [i  **  2  for  i  in  a  if  i  %  2  ==  0]

[4,  16]

We often refer to the expression as a “mapping expression”, and the if clause as a “filter clause” . i  **  2 is the

mapping expression in the above example, and i  %  2  ==  0 is the filter clause.

In this problem, we will write a function that works similarly for linked lists:

>>>  b  =  Link(1,  Link(2,  Link(3,  Link(4,  Link(5)))))

>>>  link_comp(b,  lambda  x:  x  **  2,  lambda  x:  x  %  2  ==  0)

Link(4,  Link(16))

You will implement this function both recursively and iteratively.

(a) (7.0 points) Recursive Version

Fill in the definition of the below function link_comp_recur to execute a “list comprehension” over a linked list lnk, using the functions map_func and filter_func.

map_func is a function that takes in one argument and returns one value, and filter_func is a one- argument function that will always return a boolean value.

link_comp_recur should return a new linked list that is identical to lnk, but only keeping each Link for whom calling filter_func on the first of that Link returns True. Additionally, the first of each Link

in your new list should be equal to the first of the corresponding Link in lnk with map_func applied.  Note:  filter_func is always applied before map_func—we check whether a link should be filtered before applying our mapping function to it.

def  link_comp_recur(lnk, map_func,  filter_func):

"""

>>>  lnk  =  Link(1,  Link(2,  Link(3,  Link(4,  Link(5)))))

>>>  print(lnk)

<1 2="" 3="" 4="" 5="">

>>>  add_one  =  lambda  x:  x  +  1

>>>  is_even  =  lambda  x:  x  %  2  ==  0

print(link_comp_recur(lnk,  add_one,  is_even))

<3 5="">

>>>  square  =  lambda  x:  x  **  2

>>>  greater_than_2  =  lambda  x:  x  >  2

print(link_comp_recur(lnk,  square,  greater_than_2))

<9 16="" 25="">

"""

if  __________ :

(a)

return  Link .empty

new_rest  =  __________

(b)

if  __________ :

(c)

return  __________

(d)

else:

return  new_rest

i. (1.0 pt) Fill in blank (a)

lnk is Link .empty

ii. (2.0 pt) Fill in blank (b)

link_comp_recur(lnk.rest , map_func, filter_func)

iii. (2.0 pt) Fill in blank (c)

filter_func(lnk .first)

(2.0 pt) Fill in blank (d)

Link(map_func(lnk .first), rest)

(b) (7.0 points) Iterative Version

Next, fill in the behavior of  link_comp_iter.   link_comp_iter should behave exactly the same as link_comp_recur, but internally it is implemented using iteration rather than recursion. For simplicity, you can assume that lnk will never be equal to Link .empty, and that we will never filter out every value of the list.

def  link_comp_iter(lnk, map_func,  filter_func):

"""

>>>  lnk  =  Link(1,  Link(2,  Link(3,  Link(4,  Link(5)))))

>>>  print(lnk)

<1 2="" 3="" 4="" 5="">

>>>  add_one  =  lambda  x:  x  +  1

>>>  is_even  =  lambda  x:  x  %  2  ==  0

print(link_comp_iter(lnk,  add_one,  is_even))

<3 5="">

>>>  square  =  lambda  x:  x  **  2

>>>  greater_than_2  =  lambda  x:  x  >  2

print(link_comp_iter(lnk,  square,  greater_than_2))

<9 16="" 25="">

"""

while  __________ :

(a)

lnk  =  lnk.rest

front  =  Link(map_func(lnk .first))

end  =  front

lnk  =  lnk.rest

while  lnk  is  not  Link .empty:

if  __________ :

(b)

end.rest  =  __________

(c)

__________

(d)

__________

(e)

return  front

i. (1.0 pt) Fill in blank (a)

ii.

iii.

not filter_func(lnk .first)

(2.0 pt) Fill in blank (b)

filter_func(lnk .first)

(1.0 pt) Fill in blank (c)

Link(map_func(lnk .first))

iv. (2.0 pt) Fill in blank (d)

o lnk  =  lnk .rest

o lnk .first  = map_func(lnk .first)

● end  =  end .rest

o end,  lnk  =  end .rest,  lnk .rest

o end .first  = map_func(end .first)

o end,  lnk  =  lnk,  end

v. (1.0 pt) Fill in blank (e)

lnk = lnk.rest

(c) (1.0 points) Efficiency

i. (1.0 pt) Which of the following describes the efficiency of link_comp_recur and link_comp_iter, relative to the length of the linked list lnk? Efficiency is the same for both functions.

o Constant

o Logarithmic

● Linear

o Quadratic

o Exponential

5. (15.0 points) Tails is my Pal!

(a) (3.0 points) Reverse car

Implement rev-car, a procedure that takes in a Scheme list and returns the last value in the list. You may assume the input list is not empty.

scm>  (rev-car  ! (1  2  3))

3

scm>  (rev-car  ! (1))

1

(define  (rev-car  lst)

(if  (__________)

(a)

__________

(b)

__________

(c)

)

)

i. (1.0 pt) Fill in blank (a)

ii.

iii.

(null?  (cdr lst))

(1.0 pt) Fill in blank (b)

(car lst)

(1.0 pt) Fill in blank (c)

(rev-car (cdr lst))

(b) (3.0 points) Reverse cdr

Implement rev-cdr, a procedure that takes in a Scheme list and returns a new list with all but the last element. You may assume the input list is not empty.

scm>  (rev-cdr  ! (1  2  3))

(1  2)

scm>  (rev-cdr  ! (1))

()

(define  (rev-cdr  lst)

(if  __________

(a)

__________

(b)

__________

(c)

)

)

i. (1.0 pt) Fill in blank (a)

ii.

iii.

(null?  (cdr lst))

(1.0 pt) Fill in blank (b)

nil

(1.0 pt) Fill in blank (c)

(cons (car lst)  (rev-cdr (cdr lst)))

(c) (5.0 points) Reverse cdr Tail

Now, implement rev-cdr tail recursively. reverse is a one-argument procedure that takes in a Scheme list and reverses it. You may assume reverse is implemented tail recursively and correctly for you. However, your implementation may not call reverse besides the one place where it is already written for you.

scm>  (reverse  ! (1  2  3))

(3  2  1)

scm>  (rev-cdr  ! (1  2  3))

(1  2)

scm>  (rev-cdr  ! (1))

()

(define  (rev-cdr  lst)