Due by 4pm on Wednesday, 21 March
You can grab a template for this homework either by downloading the file from the calendar or by running the following command in terminal on one of the school computers (the dot is significant: it denotes the current directory)
cp ~cs61a/lib/hw/hw9.py .
Readings. Chapter 3.2.5-6, 3.3, 3.5.1
Q1. A mobile is a type of hanging sculpture. For example, here is a picture of a mobile created by Julie Frith.
A simple binary mobile consists of two branches, left and right. Each branch is a rod of a certain length, from which hangs either a weight or another mobile. Improve the classes for Branch, Weight, and Mobile in the hw9.py file in the following ways:
A) The left and right attributes of a Mobile should both be Branch instances. Check that the types of constructor arguments for Mobile are Branch instances, and raise an appropriate TypeError for incorrect argument types.
B) The length of a Branch and the weight of a Weight should be positive numbers. Implement check_positive to check if an object x is a positive number.
- Add a property weight that gives the total weight of the mobile.
D) A mobile is said to be balanced if the torque applied by its left branch is equal to that applied by its right branch (that is, if the length of the left rod multiplied by the weight hanging from that rod is equal to the corresponding product for the right side) and if each of the submobiles hanging off its branches is balanced. Add a property method isbalanced that returns True if and only if the Mobile is balanced.
Q2. Your partner designed a beautiful balanced Mobile, but forgot to fill in the classes of each part, instead just writing T:
T(T(4,T(T(4,T(1)),T(1,T(4)))),T(2,T(10)))
The built-in Python function eval takes a string argument, evaluates it as a Python expression, and returns its value:
>>> eval('2+2')
4
>>> eval('Weight(3)').isbalanced
True
Complete the definition of interpret_mobile so that it returns a well-formed mobile by systematically guessing the class for each occurrence of T. The function should exhaustively test all possible combinations of types, handling TypeErrors until a correct series of types is found.
Warning: there are better ways to do this for real. Interpreting a large mobile is quite slow (can you say why?).
def interpret_mobile(s):
"""Return a Mobile described by string S by substituting a class
Branch, Weight, or Mobile for each occurrence of the letter 'T'.
>>> simple = 'Mobile(T(2,T(1)), T(1,T(2)))'
>>> interpret_mobile(simple).weight
3
>>> interpret_mobile(simple).isbalanced
True
>>> s = 'T(T(4,T(T(4,T(1)),T(1,T(4)))),T(2,T(10)))'
>>> m = interpret_mobile(s)
>>> m.weight
15
>>> m.isbalanced
True
"""
# YOUR CODE HERE
Q3. Complete the definition of a function subsets that returns a list of all subsets of a set \(s\). Each subset should itself be a set. (Comment: This problem is very similar to Q4 in HW#4.)
"""Return a list of the subsets of s.
>>> subsets({True, False})
[{False, True}, {False}, {True}, set()]
>>> counts = {x for x in range(10)} # A set comprehension
>>> subs = subsets(counts)
>>> len(subs)
1024
>>> counts in subs
True
>>> len(counts)
10
"""
assert type(s) == set, str(s) + ' is not a set.'
# YOUR CODE HERE
Q4. One can demonstrate that \(f(n) \in O(g(n))\) by producing values for \(p\) and \(M\) such that \(|f(n)| \le p|g(n)|\) for \(n > M\). Similarly, to show \(f(n) \in \Omega(g(n))\), show that \(|f(n)| \ge p'|g(n)|\) if \(n > M'\), for some appropriate \(p'>0\) and \(M'\). Finally, to show \(f(n)\in\Theta(g(n))\), find both pairs of values.
Use this to fill in the blanks below. In each case, try to make your values for \(M\) and \(p\) small and those for \(p'\) large. If a statement is untrue, fill in the blanks with None.
a. \(n^2 \in \Theta(4n^2 - 8n + 1)\). p = _____, M = _____, p' = ____, M' = ____
b. \(1/x \in \Omega(1)\). p' = ____, M' = ____
c. \(\sum_{k=1}^n k^2 \in O(n^3)\) p = _____, M = _____
Q5. Extend the calculator program found in hw9.py to include a new operator, word, that concatenates the string representations of two numeric arguments and treats the result as a number. The word operator takes exactly two arguments. It should raise a TypeError whenever the result of concatenation cannot be interpreted as a number.
Complete the function calc_test to verify that your changes do what they are meant to do. In this test, you will consider a series of Calculator expressions. For each one, the line following the expression gives the desired result. Compute the result that would be printed by the Calculator REPL and compare it to the target.
Q6. What are asymptotic bounds on the execution time of gaussian_solve as a function of N, the number of rows and columns in matrix A, and as a function of the total amount of data? Fill in the functions times_by_dimension and times_by_size with your solutions.
def gaussian_solve(A, b):
"""Assuming A is an NxN array of numbers and b is an N-vector
of numbers, returns vector x such that Ax = b, if possible."""
# Copy all the data into fresh lists.
x = list(b)
A = [ list(row) for row in A ]
triangularize(A, x)
diagonalize(A, x)
return x
def times_by_dimension(N):
"""A tuple L, U, where L is asymptotically proportional to the
minimum amount of time required to solve an NxN system using
gaussian solve and U is proportional to the maximum amount."""
return # YOUR SOLUTION HERE
def times_by_size(S):
"""A tuple L, U, where L is asymptotically proportional to the
minimum amount of time required to solve a gaussian_solve(A, b)
where the total amount of data in A and b is S.NxN system using
gaussian solve and U is proportional to the maximum amount."""
return # YOUR SOLUTION HERE
def triangularize(A, b):
"""Assuming A is an NxN mutable array of numbers and b is a
mutable N-vector of numbers, modify A and b into A' and b'
so that any x satisfying Ux=b' also satisfies Ax=b, where U
is the upper triangle of A' (at and above the diagonal).
The contents of the lower triangle of A' are abitrary."""
for i in range(len(A)):
pivot(A, b, i)
eliminate_lower(A, b, i)
def diagonalize(A, b):
"""Assuming A is an NxN mutable array of numbers and b is a
mutable N-vector of numbers, modify A and modify b into x such
that Ux=b', where U is the upper triangle of A. The final contents
of A are unspecified."""
for i in range(len(A)-1::-1)"
backsolve(A, b, i)
def pivot(A, b, i):
"""Exchange rows i and k>=i of A and items i and k of b so as to
maximize the resulting absolute value of |A[i][i]|."""
k = i
for j in range(i+1,len(A)):
if abs(A[j][i]) > abs(A[k][i]):
k = j
A[i], A[k], b[i], b[k] = A[k], A[i], b[k], b[i]
def eliminate_lower(A, b, i):
for j in range(i+1, len(A)):
c = A[j][i] / A[i][i]
for k in range(i+1, len(A)):
A[j][k] -= A[i][k] * c
b[j] -= b[i] * c
def backsolve(A, b, i):
for k in range(i+1, len(A)):
b[i] -= b[k]*A[i][k]
b[i] /= A[i][i]
Q7. [Extra for experts] Using reduce and lambda, define subsets using a one-line return statement.