Grading Criteria for Assignment 3

Problem 1

This one was intended to be fairly straightforward -- make sure to check the case of a list with duplicates that aren't next to each other in the list, for instance. Since the problem doesn't say either way, it's okay if they decided to sort the list first. (This can be more efficient, but definitely takes more work to code.) Here are one or two more sample inputs:

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

For reference, here's an easy solution:

def remove_duplicates(ls):
    result = []
    for x in ls:
        if x not in result:
            result.append(x)
    return result

Problem 2

Test this one out in the notebook. Try the same inputs you would have last week -- this week, they should look all fancy and HTML-y. Try copy-pasting their code into a new webpage if they did something cool with html.table.

Problem 3

It's going to be hard to carefully check the output for this one, I think. I'd try checking the output for trees with, say, 4 or 5 leaves, and then using the Catalan number formula to check the size from there. Depending on how clever the implementation is, it'll probably start to take a long time when n hits 10 or so. This one can be done using the Sage library, but here's a fairly straightforward solution independent of Sage (or anything fancy, for that matter). Note that it's not terribly clever -- it generates lots and lots of trees, but it makes sure it gets them all.

def increment_entries(t, k):
    """
    Given a tuple, returns a new tuple obtained by recurring on every
    entry. Given an integer, returns that integer plus k.
    """
    if isinstance(t, int):
        return t+k
    elif isinstance(t, tuple):
        return tuple(map(lambda x: increment_entries(x, k), t))
    else:
        raise ValueError, "wrong input type"

def all_binary_trees(n):
    if n < 2:
        return []
    elif n == 2:
        return [(0,1)]

    too_many_trees = []
    for t in all_binary_trees(n-1):
        too_many_trees.append((0, increment_entries(t, 1)))
    for t in all_binary_trees(n-1):
        too_many_trees.append((t, n-1))
    for k in range(2, n-1):
        left_trees = all_binary_trees(k)
        right_trees = all_binary_trees(n-k)
        for l in left_trees:
            for r in right_trees:
                too_many_trees.append((l, r))

    return remove_duplicates(too_many_trees)

Problem 4

This is one where you'll really need to read the code. Make sure that they actually do check the equality for every n up to the input. See if they managed to only print out a manageable amount of output -- that's by far the most time-consuming part of this problem.

Problem 5