Assignment 1:  Worth 10% of the Homework grade

Due: Monday June 15th at 3:59 pm (just before class)

To turnin program 1 (nk.py) from lectura, type
  % turnin 380assign1 nk.py

1.  Write a python module that allows us to compute n choose k
    in one of two ways: iteratively or recursively.  If you haven't
    seen n choose k before (it's very important in computer science),
    it is how many ways you can choose k items from n items.  There are a 
    number of definitions, all equivalent:

    Form 1:  (Recursive formulation)
  
     n choose k  = (n-1 choose k) + (n-1 choose k-1)  for integers with 0<k<n

    Form 2:  

                  n*(n-1)*(n-2)*...*(n-k+1)      n!
     n choose k = ------------------------- =  -------   for integers k and n
                    1 * 2 * 3 *...* k          k!(n-k)!        0<=k<=n
 

    You will be writing a Python module (called nk.py) that contains
    two functions called nchoosek_rec and nchoosek_iter that compute
    n choose k using the respective formulas.  Recursively, nchoosek_rec 
    must call itself with smaller and smaller arguments for n and k and 
    must NOT use any loops.  Iteratively, nchoosek_iter must compute
    using for loop(s) and must NOT call itself or any other functions.  
    Intuitively, just follow the definitions above.

    The program must adhere to the following guidelines:
    (1) It can be invoked from the command line and always
        requires 3 arguments: integer n, integer k, and string which
        describes how to compute it.  The program then prints the answer.
        For example:  (the % are UNIX shell prompts indicating where the 
        user types)
   
        % python nk.py 5 2 iter  
        10
        % python nk.py 5 2 rec   
        10

        If there aren't enough arguments, or the user fails to 
        supply rec or iter, the program should print the following 
        error message (using print) and exit immediately. For example:

        % python nk.py 5 1      
        Usage: nk n k rec   # Compute n choose k recursively
               nk n k iter  # Compute n choose k iteratively

        If the user mispells either rec or iter, it should
        default to iterative mode.


    (2) It can be invoked from inside of Python (and invoking it inside
        of python does NOT parse the command-line or print anything
        extraneous!)  For example: (the >>> are Python prompts)

        % python
        >>> import nk
        >>> x = nk.nchoosek_iter(5,1)
        >>> print x
        5
        >>> y = nk.nchoosek_rec(5,2)
        >>> print y
        10
        >>> help(nk)        # You should have the help page 
                            # EXACTLY as below (except for file location).
                            # You DO NOT write a help routine
                            # as you want Python will pick up your comments 
                            # in your code.

Help on module nk:

NAME
    nk - This module gives you several tools for computing n choose k.

FILE
    /Users/richismyname/cs380/nchoosek/nk.py

FUNCTIONS
    nchoosek_iter(n, k)
        Compute n choose k iteratively (with a loop and no recursion).
        n choose k = (n*(n-1)*(n-2)...(n-k+1))/(1*2*3..*k)
        for integers k and n with 0<=k<=n.  If k or n are outside this 
        range, always return 1. For example:
        >>> nchoosek_iter(5,2)
        10
        >>> nchoosek_iter(0,0)
        1
    
    nchoosek_rec(n, k)
        Compute n choose k directly from its recursive definition:
        n choose k = (n-1 choose k) + (n-1 choose k-1) for 0<k<n. 
        If k and n are outside that range, return 1.
        For example:
        >>> nchoosek_rec(5, 2)
        10
        >>> nchoosek_rec(0,0)
        1


We will be using "diff" tools to grade your program, so make sure your 
outputs match EXACTLY.  Some sample scripts will be provided.
Because we are forcing you to write a full recursive implementation,
you will find some "limitations" of the iterative vs. recursive
implementations.




To turnin program 2 (nk.c) from lectura, type
   % turnin 380assign1 nk.c
 
   2. Write a C program that computes exactly the same n choose k 
      functions from problem 1: it's input and output should match
      EXACTLY (except you only have to worry about how it operates
      from the command line).  Again, you should be writing two
      different implementations of n choose k in C: one recursive,
      one iterative.

      The program should be called "nk.c" and should compile and
      link without warnings:  
         % gcc -Wall nk.c -o nk 
      The above command should create a executable called 'nk'
      that can run very similarly to problem 1.

      It must adhere to the following guidelines:

      It can be invoked from the command line:

       % nk 5 2 iter           # compute n choose k iteratively   
       10
       % nk 5 2 rec            # compute n choose k recursively
       10 
       % nk 5                  # Error: malformed, too few arguments 
       Usage: nk n k rec   # Compute n choose k recursively
              nk n k iter  # Compute n choose k iteratively

       For grading this part of the assignment, we will be calling your
       functions using only the command line interface.   We expect the
       iterative and recursive versions to have similar properties as
       the iterative and recursive versions of the Python code.       

   
    Part 3 will be written homework to turn in at the start
    of class June 15, at 3:59 pm.

  3.  You currently have 4 versions of code to compute n choose k.
      Each version has advantages and disadvantages over the other
      versions:  Illuminate the virtues and vices of each version.  
      Consider ease of writing the code, ease of reading the code, 
      speed of execution, limitations of the machine/implementation, 
      documentation, linking issues.
      You should be able to see that no version is perfect: it's
      all about trade-offs.

      To get full credit for this part, you need to be able to quantify
      differences in speed:  time your versions and quantify the differences
      in speed.  The easiest way is to use the UNIX time command:

       % time python nk.py 100 3 rec
       161700
       0.193u 0.012s 0:00.21 95.2%	0+0k 0+0io 0pf+0w

      The four numbers reported by time are user time, system time,
      wallclock time and percent of cpu used.  The user time is what
      you should focus on, as the other times can vary tremendously 
      depending on the load of the machine. Note that this is actually a bad
      test because .193 seconds is so small, it's unclear if that time
      is just overhead (time to to invoke the program) or actual
      prgram execution.    
    
      If you do not provide timings, the most you can hope to 
      get is 60% for this part: the timings are very important,
      so be sure to characterize the differences in runtime
      accurately!