Algorithms and Data Structures 
 an exam for Gabe Lein as part of his Plan
 for Jim Mahoney and Matt Ollis

Handed out : Thursday Sep 28 2006
Due : midnight Thurs Oct 5 2006

This is an open exam: you can use any book or web sources,
as long as you cite them explicitly.  Don't ask other people
for help.  Your job is to convince us you understand the 
material.  You can use any language you like for the coding
parts of these problems, however, using a ready-made module
or package to do the bulk of the work isn't the point and
won't impress us.  All code should be documented reasonably 
well in a way that explains what the files are, how to compile 
and run them, how they work, and shows sample inputs and outputs.

As always with my exams, if you think there's a mistake
in one of the questions or it doesn't make sense, you 
can (a) ask for clarification, and/or (b) make and state
an explicit interpretation and do the problem that way.
(Again: the point is to demonstrate your understanding,
not to get the "right answer" per se.)

Good luck.

1. Big O notation
 Pick two different sorting algorithms that have different 
 asymptotic execution times as the number of items N to be 
 sorted grow.  
 (a) Explain in general terms how the algorithms work,
 and why they have that behavior.
 (b) Implement them, and show explicitly that when run
 on representative data that they exhibit the characteristics
 you've described.  
 (c) Construct a graph of time or lines executed vs N 
 and a fit from your results.
 (d) Describe what all this has to do with "P vs NP".

2. Recursion vs Iteration
 Pick two different algorithms for generating the
 perturbations of N symbols, one recursive and one iterative.
 (a) Explain both algorithms and discuss their relative
 merits in terms of speed, space, and any other features
 you deem significant.
 (b) Both recursion and iteration are common themes 
 in many algorithms.  When is one more appropriate
 than the other?  Illustrate with some examples.  
 Which category would you say the perturbation problem is in?
 (c) If time allows and the spirit moves, brownie points
 for implementing these algorithms and demonstrating them ...
 but that's not required for this on.

3. Tree search
 Write a program that builds a searches a tree 
 for one of the following two problems:
  (a) playing a simple two person game such as dots'n'boxes
  (b) solving a solitaire puzzle such as the N-puzzle or sudoku
 Be explicit about how your search algorithm is traversing
 the tree (e.g. depth first, breadth first, or whatever)
 and why you chose that strategy.  Discuss (but you don't need
 to code) what at least one other search traversal would look like.
 
4. Compression
 There are two classic lossless compression algorithms:
 LZW and Huffman.  Describe and explain both, including
  * their similarities and differences,
  * what situations each is best suited for,
  * what they have to do with the notion of "information entropy".
 While you don't have to do any coding here, some illustrative
 examples using readily available tools would not be inappropriate.