**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

Mobileshould both beBranchinstances. Check that the types of constructor arguments forMobileareBranchinstances, and raise an appropriateTypeErrorfor incorrect argument types.B) The length of a

Branchand the weight of aWeightshould be positive numbers. Implementcheck_positiveto check if an objectxis a positive number.

- Add a property
weightthat gives the total weight of the mobile.D) A mobile is said to be

balancedif 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 methodisbalancedthat returns True if and only if theMobileis 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.)

- def subsets(s):
"""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.