Lab 5: Mutability, Orders of Growth
Due by 11:59pm on Tuesday, July 13.
Starter Files
Download lab05.zip. Inside the archive, you will find starter files for the questions in this lab, along with a copy of the Ok autograder.
Topics
Consult this section if you need a refresher on the material for this lab. It's okay to skip directly to the questions and refer back here should you get stuck.
Mutability
We say that an object is mutable if its state can change as code is executed. The process of changing an object's state is called mutation. Examples of mutable objects include lists and dictionaries. Examples of objects that are not mutable include tuples and functions.
We have seen how to use the ==
operator to check if two expressions evaluate
to equal values. We now introduce a new comparison operator, is
, that
checks whether two expressions evaluate to the same values.
Wait, what's the difference? For primitive values, there is none:
>>> 2 + 2 == 3 + 1
True
>>> 2 + 2 is 3 + 1
True
This is because all primitives have the same identity under the hood. However, with non-primitive values, such as lists, each object has its own identity. That means you can construct two objects that may look exactly the same but have different identities.
>>> lst1 = [1, 2, 3, 4]
>>> lst2 = [1, 2, 3, 4]
>>> lst1 == lst2
True
>>> lst1 is lst2
False
Here, although the lists referred to by lst1
and lst2
have equal
contents, they are not the same object. In other words, they are the same in
terms of equality, but not in terms of identity.
This is important in our discussion of mutability because when we mutate an object, we simply change its state, not its identity.
>>> lst1 = [1, 2, 3, 4]
>>> lst2 = lst1
>>> lst1.append(5)
>>> lst2
[1, 2, 3, 4, 5]
>>> lst1 is lst2
True
Orders of Growth
Recall that the order of growth of a function expresses how long it takes for the function to run, and is defined in terms of the function's input sizes.
For example, let's say that we have the function get_x
which is
defined as follows:
def get_x(x):
return x
get_x
has one expression in it. That one expression takes the same
amount of time to run, no matter what x is, or more importantly, how
large x gets. This is called constant time.
The main two ways that a function in your program will get a running time different than just constant time is through either iteration or recursion. Let's start with some iteration examples!
The (simple) way you figure out the running time of a particular while loop is to simply count the cost of each operation in the body of the while loop, and then multiply that cost by the number of times that the loop runs. For example, look at the following method with a loop in it:
def foo(n):
i, sum = 1, 0
while i <= n:
sum,i = sum + i, i + 1
return sum
This loop has one statement in it sum, i = sum + i, i + 1.
This
statement is considered to run in constant time, as none of its
operations rely on the size of the input.
Individually, sum = sum + 1
and i = i + 1
are both constant time operations.
However, when we're looking at order of growth, we take the maximum of
those 2 values and use that as the running time. In 61A, we are not
concerned with how long primitive functions, such as addition,
multiplication, and variable assignment, take in order to run - we are
mainly concerned with how many more times a loop is
executed or how many more recursive calls occur as
the input increases. In this example, we execute the loop n times, and
for each iteration, we only execute constant time operations, so we get
an order of growth of linear.
Here are a couple of basic functions, along with their running times. Try to understand why they have the given running time.
Constant
def bar(n): i = 0 while i < 10: n = n * 2 return n
Logarithmic
def bar(n): i = 1 while n: i = i * 3 n = n // 2 return i
Linear
def bar(n): i, a, b = 1, 1, 0 while i <= n: a, b, i = a + b, a, i + 1 return a
Quadratic
def bar(n): sum = 0 a, b = 0, 0 while a < n: while b < n: sum += (a*b) b += 1 b = 0 a += 1 return sum
Exponential
def bar(n): if n == 0: return 1 return bar(n - 1) + bar(n - 1)
Required Questions
Mutability
Q1: List-Mutation
Test your understanding of list mutation with the following questions. What would Python display? Type it in the interpreter if you're stuck!
python3 ok -q list-mutation -u
Note: if nothing would be output by Python, type
Nothing
. If the code would error, typeError
.Relevant Topics: Mutability
>>> lst = [5, 6, 7, 8]
>>> lst.append(6)
______None
>>> lst
______[5, 6, 7, 8, 6]
>>> lst.insert(0, 9)
>>> lst
______[9, 5, 6, 7, 8, 6]
>>> x = lst.pop(2)
>>> lst
______[9, 5, 7, 8, 6]
>>> lst.remove(x)
>>> lst
______[9, 5, 7, 8]
>>> a, b = lst, lst[:]
>>> a is lst
______True
>>> b == lst
______True
>>> b is lst
______False
Q2: Map
Write a function that takes a function and a list as inputs and maps the function on the given list - that is, it applies the function to every element of the list.
Be sure to mutate the original list. This function should not return anything.
def map(fn, lst):
"""Maps fn onto lst using mutation.
>>> original_list = [5, -1, 2, 0]
>>> map(lambda x: x * x, original_list)
>>> original_list
[25, 1, 4, 0]
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q map
Q3: Swap
Implement swap
, which takes two lists and swaps their contents.
def swap(a, b):
"""Swap the contents of lists a and b.
>>> a = [1, 'two', 3]
>>> b = [4, [5, 6]]
>>> swap(a, b)
>>> a
[4, [5, 6]]
>>> b
[1, 'two', 3]
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q swap
Orders of Growth
Q4: Determining Complexity
Use Ok to test your knowledge with the following questions:
python3 ok -q wwpd-complexity -u
Be sure to ask a member of course staff if you don't understand the correct answer!
Q5: Pow
Write the following function so it runs in ϴ(log k) time.
Hint: this can be done using a procedure called repeated squaring.
def lgk_pow(n,k):
"""Computes n^k.
>>> lgk_pow(2, 3)
8
>>> lgk_pow(4, 2)
16
>>> a = lgk_pow(2, 100000000) # make sure you have log time
"""
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q lgk_pow
Submit
Make sure to submit this assignment by running:
python3 ok --submit
Optional Questions
Q6: Prime
Write a function that returns whether a number is prime or not in O(sqrt(n)) time, where sqrt means square root. You can assume n >= 2.
Hint: you don't need to check whether every single number that is smaller than n divides n
from math import sqrt
def is_prime_sqrt(n):
"""Tests whether a number N is prime or not. Implement this function
in O(sqrt(n)) time. You can assume n >= 2
>>> is_prime_sqrt(2)
True
>>> is_prime_sqrt(67092481)
False
>>> is_prime_sqrt(524287)
True
>>> is_prime_sqrt(2251748274470911)
False
>>> is_prime_sqrt(6700417)
True
>>> is_prime_sqrt(44895587973889)
False
>>> is_prime_sqrt(2147483647)
True
>>> is_prime_sqrt(67280421310721)
True
"""
# sqrt(k) will give the square root of k as a floating point (decimal)
"*** YOUR CODE HERE ***"
Use Ok to test your code:
python3 ok -q is_prime_sqrt