Problem 2: Tracing list comprehensions and recursion 50 points; individual-only

Question

Problem 2: Tracing list comprehensions and recursion

50 points; individual-only

Put your answers for this problem in a plain-text file named ps4pr2.txt.

1.Consider the following Python program:

Trace the execution of this program. Your answer should include:

a table for the variables in the global scope that illustrates how their values change over time. You can begin it as follows:

one or more separate tables that illustrate the changes in the local variables that belong to the function; you can either use a different table for each function call, or one table for the function as a whole.

Your table(s) for the function should have the following columns:

In the column for lc, you should show the how the result of the list comprehension is gradually built up. In other words, for each new value of the list comprehension’s “runner” variable, you should show the current partial result of the list comprehension.

We included a similar table for a method called myst as part of the solution to a clicker question in the lecture notes on Recursive Design.

a separate section that specifies the output of the program (i.e., the values that are printed).

2: Consider the following Python function:

Trace the execution of the following call to this function. e.g. mystery2([-2, 1, -5, 4])

Your answer should include:

a table that illustrates the changes in the values of x and scored_vals as the result of the list comprehension is gradually built up. In other words, for each new value of the list comprehension’s “runner” variable, you should show the current partial result of the list comprehension.

the value assigned to the variable bestpair

the return value of the function call

3. Briefly describe what the function mystery2 (from the previous part of this problem) does in general. In other words, for an arbitrary list of numbers vals, what will mystery2 return?

4.Consider the following recursive function:

Trace the execution of the following call to this function. e.g. mystery4('banana')

Your answer should illustrate the sequence of function calls that are made – from the initial call to the base case. Include a separate section for each call, taking an approach that is similar to the one we have often used in lecture. Begin each section with the call itself (e.g., `mystery4(‘banana’)). Then include a line that explicitly states the value assigned to the parameter. Next, if the call is a base case, you can just show the value that is returned. If the call is a recursive case, you should show the recursive call and its result, along with the value that is ultimately returned. We also encourage you to use indenting to emphasize the way in which one call occurs in the context of prior calls.

For example, recall the num_vowels function from lecture. When tracing the call num_vowels('ate'), you would start by getting all the way down to the base case:

Note that we have left blank lines between sections. Then, once you have reached the base case, you can go back and add in both the results of the recursive calls and the values returned by the earlier calls, using the space provided by the blank lines:

Take this same approach when tracing mystery4('banana').

5: What is the final result of the call mystery4('banana')?

Explanation / Answer

1)
Output of the program is:

x|y
---
5|8
15|8

global variable x and y changes(outside of the function)
x|y
---
5|4 <- before any of the mystery1() function called
5|8 <- after mystery1(y) is called
15|8 <- after mystery1(x) is called

local variable x and y changes(inside the function) while comprehending the list
range(5) gives you numbers from 0 to 4 with 4 not included. that means you have y value coming from 0..3.
x|y
---
5|-1 -> when y is 0, 2*y-1 is -1
5|1 -> when y is 1, 2*y-1 is 1
5|3 -> when y is 2, 2*y-1 is 3
5|5 -> when y is 3, 2*y-1 is 5

x|y|lc
------
5|4|              <- before any of the mystery1 function is called
5|8|[-1, 1, 3, 5] <- after mystery1(y) is called, y value changed to 8(sum(lc)) and x value remains same because inside the function lc list becomes [-1,1,3,5]
15|8|[-1, 1, 3, 5, 7] <- after mystery1(x) is called, x value changed to 15(sum(lc)) and y value remains as 8 because inside the function lc list becomes [-1, 1, 3, 5, 7]

x|y|lc
------
5|4| -> before any of the mystery1 function is called
5|4| -> when mystery1(y) is called i.e. mystery1(4) invoked
Inside the function
5|0|[-1]
5|1|[-1, 1]
5|2|[-1,1,3]
5|3|[-1,1,3,5]
function completed
5|8|

function mystery(y) is completed so sum(lc) which is -1+1+3+5 = 8 returned

x|y|lc
------
5|8| -> after mystery1(4) is completed
5|4| -> when mystery(x) is called i.e. mystery1(5) invoked. range(5) in thelist gives you numbers from 0 to 4 with 5 not included
Inside the function
5|0|[-1]
5|1|[-1, 1]
5|2|[-1,1,3]
5|3|[-1,1,3,5]
5|4|[-1,1,3,5,7]
function completed
15|8|

function mystery1(x) is completed so sum(lc) which is -1+1+3+5+7 =15 returned.

2)
output of the program is -5

scored_vals = [[x**2, x] for x in vals]
[-2, 1, -5, 4]

x|scored_vals
-------------
-2|[4,-2]
1|[[4,-2],[1,1]]
-5|[[4,-2],[1,1],[25,-5]]
4|[[4,-2],[1,1],[25,-5],[16,4]]
after list comprehension, max(scored_vals) will be [25,-5]
[25, -5] -> best_pair list
when it returns best_pair[1] it means -5 is the value

3)
mystery2 function actually is trying to get a pair which has the maximum value when squared and returns that element. For example, the list (1,2,3) will have pairs like [[1,1],[4,2],[9,3]] which in this case best pair is [9,3] and the value returned from function is 3. This is what the function does.

def mystery4(s):
    """ takes a string s and does something with it """
    if len(s) <= 1:
        return ''      # the empty string, with nothing between the quotes
    else:
        result_rest = mystery4(s[1:])
        if s[0] == s[-1]:
            return result_rest
        else:
            return result_rest + s[0]
4)
mystery4('banana')
------------------
s='banana'
result_rest = mystery4('anana')

mystery4('anana')
-----------------
s='anana'
result_rest = mystery4('nana')

mystery4('nana')
----------------
s='nana'
result_rest = mystery4('ana')

mystery4('ana')
---------------
s='ana'
result_rest = mystery4('na')

mystery4('na')
--------------
s='na'
result_rest = mystery4('a')

mystery4('a')
-------------
s='a'

Once length of s is <=1 the function will return empty string and the if-else part will start.

mystery4('banana')
------------------
s='banana'
result_rest = mystery4('anana') = 'nn'
result_rest = 'nn' + s[0] = 'nn' +'b' = 'nnb' -> else condition matches here

mystery4('anana')
-----------------
s='anana'

result_rest = 'nn' -> if condition matches here

mystery4('nana')
----------------
s='nana'
result_rest = 'n' + s[0] -> else condition matches here
result_rest = 'n' + 'n' = 'nn'

mystery4('ana')
---------------
s='ana'
result_rest = 'n' -> if condition matches here

mystery4('na')
--------------
s='na'
result_rest = 'na'
result_rest = '' + 'n' = 'n' -> else condition matches here

mystery4('a')
-------------
s='a'
result_rest = ''

5) nnb
As explained above the final result of function is 'nnb'

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.