Grading Criteria for Assignment 1

Problem 1

There are a handful of things that you could say are wrong with collatz.py. Here are two obvious problems:

Goes into an infinite loop for non-positive input (try collatz(0))
Error about stack overflow if input large (e.g. collatz(10**100))

In general, I'm willing to allow people to list as bugs things that usually fall under the heading of "style" -- for instance, weird error messages if you call the function with a string, no docstring, that kind of stuff.

Problem 2

The sky's the limit here. A few things I'd want to do:

Return information about the list: max, length, that kind of stuff
Write something that takes a sequence and runs collatz for each
- element, reporting on what it finds
Write something that memoizes, i.e. caches values it's seen before
- and doesn't call the function again
Rewrite it so that it doesn't blow the stack.

Problem 3

Again, pretty much anything goes here. I'm guessing most people will mention something involving trying to find extrema, i.e. unusually long or short sequences, that kind of thing.

Problem 4

There are a million ways to do this. Here's the shortest one I can think of:

def f(n):
    if n == 1:
        print "hi mom"
        print "bye mom"

def g(n):
    if n == 1:
        print "hi mom"
    print "bye mom"

This produces different behavior for any input except n=1. Of course, this uses side-effects (printing), which isn't necessary:

def f(n):
    ls = []
    if n == 1:
        ls.append(3)
        ls.append(5)
    return ls

def g(n):
    ls = []
    if n == 1:
        ls.append(3)
    ls.append(5)
    return ls

== Problem 5 ==

First, note that the problem did not say anything about returning a "sensible" collection of change. So, for instance, here's a really simple solution:

def cashier(n):
    """
    Takes an integer n between 1 and 100 as input, and returns a list
    of the strings "penny", "nickel", "dime", and "quarter" whose
    value in US dollars is n.
    """
    return ['penny'] * n

Smarter solutions will use other coins. :)

There's an interesting question that comes up here: the "natural" algorithm is to give as many quarters as possible, then dimes, etc. Does this always give the smallest possible number of coins? It turns out the answer is "yes"; if you make certain kinds of restrictions (different coins, only so many of each, etc.), then this won't always return the fewest coins.

You should try out a bunch of inputs with their code; if you're feeling adventurous, just write a for loop that tries everything -- it might look something like this:

for i in range(1, 101):
    print "Trying %s:"%i
    print cashier(i)
    print

Of course, you still have to actually check the results; if they return a list, this might be easy. If they simply print something out, it'll probably be harder.

Problems 6 and 7