$24
Homework 3 Solution
In this homework, you’ll explore the language features and semantics of Python 3.x in more detail. Each question has a time estimate; you’ll know you're ready for the exam when you can solve them roughly within their time constraints.
You will be expected to be familiar with all of the concepts covered in this homework and be able to write grammatically-correct Python code for the exam. We understand, however, that as you learn these questions may take more time. For that reason, only starred red questions need to be completed when you submit this homework (the rest should be used as exam prep materials). Note that for some multi-part questions, not all parts are marked as red.
For questions where you are writing Python code, you do not need to perform type-checking of parameters unless explicitly instructed to.
You must turn in a PDF file with your answers via Gradescope - you may include both typed and hand-written solutions, so long as they are legible and make sense to our TAs. Make sure to clearly label each answer with the problem number you’re solving so our TAs can more easily evaluate your work.
1. ** (3 min.) Consider the following function that takes in a list of integers (either 0 or 1) representing a binary number and returns the decimal value of that number. Fill in the blanks in the list comprehension so the function works correctly.
Example:
convert_to_decimal([1, 0, 1, 1, 0]) should return 22.
convert_to_decimal([1, 0, 1]) should return 5.
from functools import reduce
def convert_to_decimal(bits):
exponents = range(len(bits)-1, -1, -1)
nums = [_______________ for ________ in zip(bits, exponents)]
return reduce(lambda acc, num: acc + num, nums)
2. **
a) (5 min.) Write a function named parse_csv that takes in a list of strings named lines. Each string in lines contains a word, followed by a comma, followed by some number (e.g. "apple,8"). Your function should return a new list where each string has been converted to a tuple containing the word and the integer (i.e. the tuple should be of type (string, int)). Your function’s implementation should be a single, one-line nested list comprehension.
Example:
parse_csv(["apple,8", "pear,24", "gooseberry,-2"] should return [("apple", 8), ("pear", 24), ("gooseberry", -2)].
Hint: You may find list unpacking useful.
b) (2 min.) Write a function named unique_characters that takes in a string sentence and returns a set of every unique character in that string. Your function’s implementation should be a single, one-line set comprehension.
Example:
unique_characters("happy") should return {"h", "a", "p", "y"}.
c) (2 min.) Write a function named squares_dict that takes in an integer lower_bound and an integer upper_bound and returns a dictionary of all integers between lower_bound and upper_bound (inclusive) mapped to their squared value. You may assume lower_bound is strictly less than upper_bound.
Your function’s implementation should be a single, one-line dictionary comprehension.
Example:
squares_dict(1, 5) should return
{1: 1, 2: 4, 3: 9, 4: 16, 5: 25}.
3. ** (4 min.) Consider the following function that takes in a string sentence and a set of characters chars_to_remove and returns sentence with all characters in chars_to_remove removed. Fill in the blank so the function works correctly. You may not use a separate helper function.
Hint: You may find some of the concepts we learned in our functional programming discussions useful .
Example:
strip_characters("Hello, world!", {"o", "h", "l"}) should return "He, wrd!"
def strip_characters(sentence, chars_to_remove):
return "".join(____________________________________________________)
4. ** (8 min.) Consider the following Python script:
class Box:
def __init__(self, value):
self.value = value
def quintuple(num):
num *= 5
def box_quintuple(box):
box.value *= 5
num = 3
box = Box(3)
quintuple(num)
box_quintuple(box)
print(f"{num} {box.value}")
Running this script yields the output:
3 15
Explain, in detail, why box’s value attribute was mutated but num was not. Your answer should explicitly mention Python’s parameter passing semantics.
Hint: Check out the Python documentation to understand where class instances store their attributes.
5. ** (5 min.) Consider the following output from the Python 3 REPL:
>>> class Foo:
... def __len__(self):
... return 10
...
• len(Foo())
10
• len("blah")
4
• len(5)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: object of type 'int' has no len()
Explain why Python allows you to pass an object of type Foo or str to len, but not one of type int. Your answer should explicitly reference Python’s typing system.
6. Consider the following Duck class, and two functions that check whether or not an object is a Duck:
class Duck:
def __init__(self):
pass # Empty initializer
def is_duck_a(duck):
try:
duck.quack()
return True
except:
return False
def is_duck_b(duck):
return isinstance(duck, Duck)
a) (2 min.) Write a new class such that if we passed an instance of it to both functions, is_duck_a would return True but is_duck_b would return False.
b) (2 min.) Write a new class such that if we passed an instance of it to both functions, is_duck_a would return False but is_duck_b would return True.
c) (5 min.) Which function is more Pythonic: is_duck_a or is_duck_b? This reference may help provide some insight.
7.
a) ** (3 min.) Consider the following function that takes in a list of integers and another integer k and returns the largest sum you can obtain by summing k consecutive elements in the list. Fill in the blanks so the function works correctly.
Example:
largest_sum([3,5,6,2,3,4,5], 3) should return 14. largest_sum([10,-8,2,6,-1,2], 4) should return 10.
def largest_sum(nums, k):
if k < 0 or k > len(nums):
raise ValueError
elif k == 0:
return 0
max_sum = None
for i in range(len(nums)-k):
sum = 0
for num in _________:
sum += num
if _______________________:
max_sum = sum
return max_sum
b) (3 min.) The function in part a) runs in O(nk) time where n is the length of nums, but we can use the sliding window technique to improve the runtime to O(n).
Imagine we know the sum of k consecutive elements starting at index i. We are interested in the next sum of k consecutive elements starting at index i+1. Notice that the only difference between these two sums is the element at index i (which becomes excluded) and the element at index i+k (which becomes included).
We can compute each next sum by subtracting the number that moved out of our sliding window and adding the one that moved in. Fill in the blanks so the function works correctly.
def largest_sum(nums, k):
if k < 0 or k > len(nums):
raise ValueError
elif k == 0:
return 0
sum = 0
for num in _________:
sum += num
max_sum = sum
for i in range(0, len(nums)-k-1):
sum -= _________
sum += _________
max_sum = max(sum, max_sum)
return max_sum
8. ** We're going to design an event-scheduling tool, like a calendar. Events have a start_time and an end_time. For simplicity, we will model points in time using ints that represent the amount of seconds past some reference time (normally, we would use the Unix epoch, which is January 1, 1970).
a) (3 min.) Design a Python class named Event which implements the above functionality. Include an initializer that takes in a start_time and end_time. If start_time >= end_time, raise a ValueError.
The following code:
event = Event(10, 20)
print(f"Start: {event.start_time}, End: {event.end_time}")
try:
invalid_event = Event(20, 10)
print("Success")
except ValueError:
print("Created an invalid event")
should print:
Start: 10, End: 20
Created an invalid event
b) (3 min.) Write a Python class named Calendar that maintains a private list of scheduled events named _events.
It should:
◦ Include an initializer that takes in no parameters and initializes _events to an empty list.
◦ Have a method named get_events that returns the _events list.
◦ Have a method named add_event that takes in an argument event:
▪ If the argument is not of type Event, do nothing and raise a
TypeError.
▪ Otherwise, add the event to the end of the events list.
The following code:
calendar = Calendar()
print(calendar.get_events())
calendar.add_event(Event(10, 20))
print(calendar.get_events()[0].start_time)
try:
calendar.add_event("not an event")
except TypeError:
print("Invalid event")
should print:
[]
10
Invalid event
c) (3 min.) Consider the following subclass of Calendar:
class AdventCalendar(Calendar):
def __init__(self, year):
self.year = year
advent_calendar = AdventCalendar(2022)
print(advent_calendar.get_events())
Running this code as-is (assuming you have a correct Calendar implementation)
yields the following output:
AttributeError: 'AdventCalendar' object has no attribute
'_events'. Did you mean: 'get_events'?
Explain why this happens, and list two different ways you could fix the code within the class so the snippet instead prints:
[]
9. ** (4 min.) Show, by example, whether or not Python supports closures. Briefly explain your reasoning.
10. Suppose we have 2 languages. The first is called I-Lang and is an interpreted language. The interpreter receives lines of I-Lang and efficiently executes them line by line. The second is called C-Lang and is a compiled language. Assume that it takes the same time to write an I-Lang script as a C-Lang program if both perform the same function.
a) (2 min.) Suppose we have an I-Lang script and a C-Lang executable that functionally perform the exact same thing. If we execute both at the same time, which do you expect to be faster and why?
b) (2 min.) Suppose Jamie and Tim are two equally competent students developing a web server that sends back a simple, plaintext HTML page. Jamie writes her server in I-Lang, whereas Tim writes his in C-Lang. Assuming that the server will be deployed locally, who will most likely have the server running first, and why?
c) (2 min.) Jamie and Tim have a socialite friend named Connie who uses a fancy new SmackBook Pro. The SmackBook Pro has a special kind of chip called the N1, which has a proprietary machine language instruction set (ISA) completely unique to anything else out there. If you are familiar with Rosetta, assume the SmackBook Pro has no built-in emulator/app translator. Jamie and Tim have less-fancy computers with Intel chips.
Connie has a native copy of the I-Lang interpreter on her computer. Jamie sends Connie her web server script, and Tim sends Connie his pre-compiled executable. Will Connie be able to execute Jamie’s script? What about Tim’s executable?
10. (10 min.) Consider the following code snippet that compares the performance of matrix multiplication using a hand-coded Python implementation versus using numpy:
import numpy as np import time
from random import randint
def dot_product(a, b): result = 0
for a_i, b_i in zip(a, b): result += a_i * b_i
return result
def matrix_multiply(matrix, vector):
return [dot_product(row_vector, vector) for row_vector in matrix]
◦ Generate a 1000 element vector, and a 1000 x 1000 element matrix vector = [randint(0, 10) for _ in range(1000)]
matrix = [[randint(0, 10) for _ in range(1000)] for _ in range(1000)]
◦ Create numpy arrays
np_vector = np.array(vector)
np_matrix = np.array(matrix)
• Multiply the matrix and vector (using our hand-coded implementation) start = time.time()
matrix_multiply(matrix, vector) end = time.time()
• Multiply the matrix and vector (using numpy)
np_start = time.time()
np_matrix.dot(np_vector)
np_end = time.time()
print(f"Hand-coded implementation took {end - start} seconds")
print(f"numpy took {np_end - np_start} seconds")
If we run this code, the numpy operation is invariably about 100 times faster than the call to matrix_multiply:
Hand-coded implementation took 0.043227195739746094 seconds numpy took 0.0004067420959472656 seconds
Assuming that the implementations of dot_product and matrix_multiply are reasonably optimized, provide an explanation for this discrepancy in performance.
Hint: Take a look at this page from the numpy docs to understand a bit more about how the package is implemented.
