Due at 11:59:59 pm on 09/24/2019.

Starter Files

Download lab03.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the OK autograder.

Submission

By the end of this lab, you should have submitted the lab with python3 ok --submit. You may submit more than once before the deadline; only the final submission will be graded. Check that you have successfully submitted your code on okpy.org. See this article for more instructions on okpy and submitting assignments.

• To receive full credit for this lab, all questions must be attempted.

When you are ready to submit, run ok with the --submit option:

python3 ok --submit

After submitting, ok will display a submission URL, with which you can view your submission on okpy.org.

Last lab, we went over how to use python tutor to help us visualize the execution of python code. Let's do another example to review the concept of scopes for variables and nesting for functions.

Scopes and Nested Functions

Let’s see what nested function calls look like in the python interpreter.

PythonTutor

Paste this code into the interpreter or follow this link Ex1

def bonus(score):
    previousScore = score
    multiplier = 1
    if score > 25:
      multiplier = 2
    score *= multiplier
    return score
print(bonus(score))
print(previousScore)

Now step through the code. Why does it error out? The error message reads

NameError: name 'previousScore' is not defined

But didn't we define previousScore in the body of the bonus function? We did, but that previousScore is only defined in the scope of the function. So it is not accessible outside in the global scope.

Let's try another function Ex2

def totalScore(score):
    multiplier = 2
    def bonus(score):
      if score > 25:
        score *= multiplier
      else:
        score /= multiplier
      return score
  return score, bonus(score)
score = 12
totalScore(score)
print(score)

There's a lot to unpack here. We purposefully gave the variables the same names so you can see how python lookups values for variables. The general principle is that python looks for the value in the current scope first. If it can't find the variable there, it checks it's parent scope, and the parent's parent, all the way up to the global scope. If the variable still isn't found there, an error is raised. Walk through the lookup for multiplier on line 7 in your head as a sanity check.

Lists

In Data 8, you have recently started working with Tables. Tables are an extremely useful and powerful data type. In CS88 we will work with other data types. Python provides several important built-in data types that we can build from. So far, you have met numberical data types (ints, floats, and booleans) and one sequence type (strings). Lists, tuples, and dictionaries are other sequence data types in Python. Here, we will take a closer look at lists. A list can contain a sequence of values of any type.

You can create a list just by placing the values, separated by commas, within square brackets. Here are some examples. As you will see in one of the examples, lists can contain other lists.

>>> [1,2,3]
[1, 2, 3]
>>> ["frog", 3, 3.1415]
['frog', 3, 3.1415]
>>> [True, [1, 2], 42]
[True, [1, 2], 42]

Open up your python interpreter and create some lists of your own.
You learned last week that what really makes a data type useful is the operations that you can perform on it. What can you do with lists?

>>> x = [1,2,3]    # assign them to variables
>>> len(x)         # get their length, i.e., the number of elements in them
3
>>> x + [4,5]      # + is concatenation
[1, 2, 3, 4, 5]
>>> [1,2] * 3        # * is replication
[1, 2, 1, 2, 1, 2]
>>> len([1,2] * 3)
6
>>> [1,2] * [3,4]    # what's this?
TypeError: can't multiply sequence by non-int of type 'list'

The in operator is very useful when working with lists. It operates on the entire list and produces a boolean that answers the question, "Is this item in the list?".

>>> 2 in [1,2,3]
True
>>> "frog" in [1,2,3]
False
>>> [1,2] in [1,2,3]
False
>>> [1,2] in [[1,2],3]
True

Question 1: Second Max

Write a function that finds the second highest number in a list of positive integers. You can assume that the list always has at least two integers.

def second_max(lst):
    """ 
    Return the second highest number in a list of positive integers.

    >>> second_max([3, 2, 1, 0])
    2
    >>> second_max([2, 3, 3, 4, 5, 6, 7, 2, 3])
    6
    >>> second_max([1, 5, 5, 5, 1])
    5
    >>> second_max([5, 6, 6, 7, 1])
    6
    >>> second_max([5, 6, 7, 7, 1])
    7
    """

    "*** YOUR CODE HERE ***"
    highest = 0
    second_highest = 0
    for num in lst:
        if num >= highest:
            second_highest = highest
            highest = num
        elif num < highest and num > second_highest:
            second_highest = num
    return second_highest

Toggle Solution

Use OK to test your code:

python3 ok -q second_max

List Comprehensions

Now that we can create lists, assign variables, write expressions, and define functions, we can compose these concepts to do lots of interesting things. Python's list comprehensions open a beautiful world of data-centric programming.
The comprehension is in brackets, just like a list, but rather than a static sequence of literals, it is a dynamically computed list.

>>> somelist = [1, 2, 9, -1, 0]
>>> [x+1 for x in somelist]
[2, 3, 10, 0, 1]
>>> [x*x for x in somelist]
[1, 4, 81, 1, 0]

In general, the expression just inside the [ is evaluated for each element in the list, using the variable between the for and the in to name each element in succession. The result is the transformed list.

>>> def square(x):
...     return x*x
...
>>> def squares(s):
...     return [square(x) for x in s]
...
>>> squares([0,1,2,4])
[0, 1, 4, 16]

>>>x, y = 2, 3
>>> x+y
5
>>> [x+y for x,y in [[1,2], [2,3], [3,4]]
[3, 5, 7]

This is a powerful design pattern, called map, that you will use in often in analyzing data. It maps, or transforms, one data structure into another under some expression, often by applying a function to each of the elements.

Do you remember the Table.apply( ) function from Data 8? The Table.apply function is another great example of the map design pattern as it applies a "transformation" or a function to a row or column.

Sometimes you need a sequence to get started, and Python provides handy tools for that. One of them is range.

>>> [x*x for x in range(10)]
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

You can review range in Section 2.3 of Composing Programs.

Question 2: Perfect squares

Implement the function squares, which takes in a list of positive integers, and returns a new list which contains only elements of the original list that are perfect squares. Use a list comprehension.

from math import sqrt

def is_square(n):
    return float(sqrt(n)) == int(sqrt(n))

def squares(seq):
    """Returns a new list containing elements of the original list that are
    perfect squares.

    >>> seq = [49, 8, 2, 1, 102]
    >>> squares(seq)
    [49, 1]
    >>> seq = [500, 30]
    >>> squares(seq)
    []
    """
    "*** YOUR CODE HERE ***"
    
    return [n for n in seq if is_square(n)]

Toggle Solution

Use OK to test your code:

python3 ok -q squares

Question 3: Perfect Pairs

Implement the function pairs, which takes in an integer n, and returns a new list of lists which contains pairs of numbers from 1 to n. Use a list comprehension.

def pairs(n):
    """Returns a new list containing two element lists from values 1 to n
    >>> pairs(1)
    [[1, 1]]
    >>> x = pairs(2)
    >>> x
    [[1, 1], [2, 2]]
    >>> pairs(5)
    [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]]
    >>> pairs(-1)
    []
    """
    "*** YOUR CODE HERE ***"
    
    return [[i, i] for i in range(n + 1)]

Toggle Solution

Use OK to test your code:

python3 ok -q pairs

Conditionals

You can review the syntax and behavior of if statements in Section 1.5.4 of Composing Programs.

The conditional statement is a statement, not an expression; it does not return a value. The if-expression (or predicate) is evaluated first, before any other part of the statement, to determine whether to evaluate an arm. If the if-expression evaluates to a True value then the statement(s) following the : is evaluate. Otherwise, the else arm is evaluated, if present. Multiple predicates can be chained together with elif. They are evaluated sequentially. Often conditionals are often used along with return statements in functions. For example, in some census data you see in c8 you might want to decode the gender code.

def decode_gender(code):
    if (code == 0):
        return 'all'
    elif (code == 1):
        return 'male'
    elif (code == 2):
        return 'female'
    else:
        return 'unknown'

Conditionals are often used with assignment statements to simplify later expressions.

if ((year % 4) == 0) and (((year % 100) != 0) or ((year % 400) == 0)):
    year_len = 366
else:
    year_len = 365
<do something with year_len>

Or with print statements to control output

if (scene == 'architect skit'):
    print("spam, spam, spam")
else
    print("nobody expects the Spanish inquisition")

Omitting the else

Consider the following function:

def abs(x):
    if x >= 0:
        return x
    else:
        return -x

It is correct to rewrite abs in the following way:

def abs(x):
    if x >= 0:
        return x
    return -x

This is a direct consequence of how return works — when Python sees a return statement, it will immediately terminate the function, and the rest of the function will not be evaluated. In the above example, if x >= 0, Python will never reach the final line. Try to convince yourself that this is indeed the case before moving on.

Keep in mind that omitting the else only works if the function is terminated! For example, the following function will always print "less than zero", because the function is not terminated in the body of the if suite:

>>> def foo(x):
...     if x > 0:
...         print("greater than zero")
...     print("less than zero")
...
>>> foo(-3)
less than zero
>>> foo(4)
greater than zero
less than zero

In general, omitting the else will make your code more concise — however, if you find that it makes your code harder to read, by all means use an else statement.

Question 4: Where Above

Lets use list comprehensions to implement some of the filters we could apply in Data 8's table.where() function. In particular, fill in the where_above function that returns a list that filters out any elements less than or equal to limit. Try to do this in only one line.

def where_above(lst, limit):
    """
    where_above behaves like table.where(column, are.above(limit)).
    The analogy is completed if you think of a column of a table as a list and return the filtered column instead of the entire table.

    >>> where_above([1, 2, 3], 2)
    [3]
    >>> where_above(range(13), 10)
    [11, 12]
    >>> where_above(range(123), 120)
    [121, 122]

    """
    "*** YOUR CODE HERE ***"
    
    return [n for n in lst if n > limit]

Toggle Solution

Use OK to test your code:

python3 ok -q where_above

Iteration: For loops

You might remember for loops from simulations in Data 8. A for loop can be constructed by using the for statement. Typically, the for statement is used to iterate through a sequence, such as a list, and perform some computing on each iteration. Here is an example:

def sum(s):
   """
   Return the sum of the elements in the sequence, s.
   >>> sum([1, 2, 3])
   6
   """
   total = 0           
   for number in s:         # for each element in the sequence
      total = total + number  # accumulate it into the partial sum
   return total         # the final partial sum is the total sum

The line total = total + number is called an accumulation statement. This statement is so common that it has a special shorthand notation.

total += number

Question 5: Minmax

In c8 you often need to understand the spread of data. Write a simple function to find the minimum and maximum elements in a sequence using a for loop. You CANNOT use any in-built functions.

def minmax(s):
    """Return the minimum and maximum elements of a non-empty list. Hint: start 
    with defining two variables at the beginning. Do not use the built in 
    max or min functions

    >>> minmax([1, 2, -3])
    [-3, 2]
    >>> x = minmax([2])
    >>> x
    [2, 2]
    >>> minmax([4, 5, 4, 5, 1, 9, 0, 7])
    [0, 9]
    >>> minmax([100, -10, 1, 0, 10, -100])
    [-100, 100]
    """
    "*** YOUR CODE HERE ***"
    
    mn, mx = s[0], s[0]
    for x in s:
        if mn is None or x < mn:
            mn = x
        if mx is None or x > mx:
            mx = x
    return [mn, mx]

Toggle Solution

Use OK to test your code:

python3 ok -q minmax

Iteration: While loops

Python also has a more basic iteration construct that is closely related to conditionals, the while loop. It does not make any assumption of iterating through a sequence. It iterates until a predicate is satisfied.

You can review the syntax of while loops in Section 1.5.5 of Composing Programs.

Typically, some state will be established before the while loop. The predicate will compute a boolean expression involving that state. And the body of the loop will advance the state, thereby iterating until the predicate is satisfied.

Question 6: Closest Power of 2

Let's test out our knowledge by making a function that finds the largest power of 2 that is less than a given number. Fill in the function closest_power_2 below to return the closest power of 2 using a while loop.

def closest_power_2(x):
    """ Returns the closest power of 2 that is less than x
    >>> closest_power_2(6)
    4
    >>> closest_power_2(32)
    16
    >>> closest_power_2(87)
    64
    >>> closest_power_2(4095)
    2048
    >>> closest_power_2(524290)
    524288
    """
    "*** YOUR CODE HERE ***"
    
    exponent = 0
    while x > (2 ** (exponent + 1)):
        exponent += 1
    return 2 ** exponent

Toggle Solution

Use OK to test your code:

python3 ok -q closest_power_2

Here's some food for thought: What mathematical operation is closely related to finding the closest power of 2? It's the logarithm! (at least with a base of 2) By keeping track of which power of 2 you are on, you can compute rounded down version of log base 2 of numbers using your closest_power_2 function. If this stuff is cool to you, you should check out CS61C, particularly the sections on binary representations of data, and bitwise operators.