Sharedwww / wiki / 10(2f)480b(2f)assignments(2f)assn3.htmlOpen in CoCalc
Author: William A. Stein
10/480b/assignments/assn3
 [top] [TitleIndex] [WordIndex]

10/480b/assignments/assn3

Assignment 3, Due 4/30

Do at least four of the following problems.

Problem 1

Write a function remove_duplicates that takes as input a list, and returns a new list which contains exactly one copy of each entry in the input list. Here's an example:

>>> remove_duplicates([3,3,3,3])
[3]
>>> remove_duplicates([3, [3]])
[3, [3]]
>>> remove_duplicates([3, [3], [3]])
[3, [3]]

As a side note, you may find the in operator useful:

>>> 3 in [3]
True
>>> [3] in [3]
False
>>> [3] in [[3]]
True

Problem 2

This one is a new spin on a problem from last week. Take your solution from print_table on last week's homework and create an @interact that has input fields for a list and a function, and prints a nice table (just as in last week's homework). If that's too easy, create something that will print the table, and then print out correct HTML code for typesetting that table (so that you could copy-paste it into a webpage). You might find sage's html.table command helpful for this part.

Problem 3

Create a function that takes a positive integer n as input, and returns a list containing all binary trees with exactly n leaves.

You can approach this two ways:

  • you could try to "roll your own" code, which simply generates the list of all trees, or
  • dig into the Sage documentation, and find out how to use Sage to do this. (Hint: you'll want to start by looking into the combinatorics module, which is located in sage.combinat.)

If you're going with the "roll your own" approach, it might help to realize that there's a one-to-one correspondence between binary trees with n leaves and ways of parenthesizing the expression x1 * x2 * ... * xn. This means that you could represent each tree as a really nested tuple: for instance, letting (((x1 x2)(x3(x4 x5)))x6) correspond to (((1, 2), (3, (4, 5))), 6).

You can represent the trees in any way you'd like, as long as you document it. Make sure that your output is complete and contains no duplicates. If you're curious, the number of such trees is known as the nth Catalan number, which you can find out more about on the Wikipedia article.

Problem 4

You may have seen the amusing fact that (1+2+...+n)^2 = 1^3 + 2^3 + ... + n^3. One can prove this several ways, with induction being the most common. (There's also an amusing visual proof.) However, let's say you saw this for the first few values of n, and wanted to check out more. Write a program which takes as input a positive integer n and verifies this fact for every positive integer up to and including n. (That is, compute both sides and check that they match.) You should print some output as you go -- but printing something for every single integer would probably be overkill. Try to print a manageable amount of data.

Problem 5

This is a two-part problem, to design a class and use it as a decorator.

First, we'll make a new class called file_logger. We want to be able to use this as a decorator, as follows:

>>> my_logger = file_logger("some_filename")
>>> @my_logger
... def f(n, m):
...     do_stuff()
...     return something_interesting
...

Now every call to f will act just like normal -- except that it will log all inputs and outputs to the file some_filename.

This should be implemented as a Python class with at least two methods: __init__ and __call__. The __init__ method should take two arguments: self (which methods on a class almost always take), and filename, which is the file where it should log inputs and outputs. The __call__ method should take a single argument, a function, and should return a new function which takes the same arguments (think *args, **kwds) and logs all inputs and outputs to the file filename.


2013-05-11 18:32