Advanced Programming, Fall 2014
HW1 - Python and Basic Data Structures
Due electronically on Blackboard on Sunday Sep 21, 9pm.

*** No late HW will be accepted. ***

*** Quiz 1 (Monday Sep 22) will mostly depend on HW1. ***

Include in your submission a report.txt and all python programs.

Expected Amount of Work for an average student: 6-8 hours.

Textbooks for References:
[1] CLRS Ch. 9.2 and Ch. 12

0. Implement a recursive and memoized Fibonacci function.
   
   What is the time complexity *before* memoization? 
   What is the new complexity *after* memoization?

1. Implement a recursive mergesort.

   What is the worst-case complexity?

2. In the slides we showed a buggy version of qsort which is weird in an interesting way:
   it actually returns a binary search tree (BST) for the given array, where the root is the pivot.

   e.g., 
   >>> tree = sort([4,2,6,3,5,7,1,9])
   >>> tree
   [[[[], 1, []], 2, [[], 3, []]], 4, [[[], 5, []], 6, [[], 7, [[], 9, []]]]]

   which encodes a binary search tree:

                      4
                    /   \
                  2       6
                 / \     / \
                1   3   5   7
                             \
                              9
   
   Now on top of that piece of code, add three functions: 
   * sorted(t): returns the sorted order (infix traversal)
   * search(t, x): return whether x is in t
   * insert(t, x): if x is absent, insert it into t (in-place), otherwise do nothing.
   * delete(t, x): if x is in the tree, delete it, and make sure the resulting tree is still a BST;
     	       	   otherwise do nothing.

   >>> sorted(tree)
   [1, 2, 3, 4, 5, 6, 7, 9]
   >>> search(tree, 6)
   True
   >>> search(tree, 6.5)
   False
   >>> insert(tree, 6.5)
   >>> tree
   [[[[], 1, []], 2, [[], 3, []]], 4, [[[], 5, []], 6, [[[], 6.5, []], 7, [[], 9, []]]]]
   >>> insert(tree, 3)
   >>> tree
   [[[[], 1, []], 2, [[], 3, []]], 4, [[[], 5, []], 6, [[[], 6.5, []], 7, [[], 9, []]]]]
   >>> delete(tree, 4)
   >>> tree
   [[[[], 1, []], 2, []], 3, [[[], 5, []], 6, [[[], 6.5, []], 7, [[], 9, []]]]]

   (or    [[[[], 1, []], 2, [[], 3, []]], 5, [[], 6, [[[], 6.5, []], 7, [[], 9, []]]]])

   Hint: search, insert, and delete should all depend on a helper function _search(tree, x) which 
   returns the subtree (a list) rooted at x when x is found, or the [] where x should be inserted.

   e.g., 
   >>> tree = sort([4,2,6,3,5,7,1,9])        # starting from the initial tree
   >>> _search(tree, 3)
   [[], 3, []]
   >>> _search(tree, 0)
   []
   >>> _search(tree, 6.5)
   []
   >>> _search(tree, 0) is _search(tree, 6.5)
   False
   >>> _search(tree, 0) == _search(tree, 6.5)
   True
   
   Note the last two []'s are different nodes (with different memory addresses): 
   the first one is the left child of 1, while the second one is the left child of 7
   (so that insert is very easy).
   
   Filename: qsort.py


3. Quickselect with Randomized Pivot (CLRS Ch. 9.2).

   >>> qselect(2, [3, 10, 4, 7, 19])
   4
   >>> qselect(4, [11, 2, 8, 3])
   11

   What's the time complexity? Briefly explain.

   Filename: qselect.py
 

Debriefing (required in report.txt!): --------------------------

1. Approximately how many hours did you spend on this assignment?
2. Would you rate it as easy, moderate, or difficult?
3. Did you work on it mostly alone, or mostly with other people?
4. How deeply do you feel you understand the material it covers (0%–100%)? 
5. Any other comments?

This section is intended to help us calibrate the homework assignments. 
Your answers to this section will *not* affect your grade; however, skipping it
will certainly do.