Advanced Programming, Spring 2014
HW1 - Python and Basic Data Structures
Due electronically on Blackboard on Tuesday Feb 4, 11:59pm.

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

Expected Amount of Work for an average student: 7-9 hours.

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

1. (updates: some questions are moved to the extra credit section, which includes a new subproblem).

   In the lectures we did memoized Fibonacci, and now it's your turn to implement 
   memoized Ackermann:

   http://en.wikipedia.org/wiki/Ackermann_function

            n+1			if m=0
   A(m,n) = A(m-1, 1)		if m>0 and n=0
   	    A(m-1, A(m, n-1))	if m>0 and n>0

   Simply define a naive function A and its memoized version A2 in file ackermann.py, 
   so that when I test I just need to:

   >>> from ackermann import A
   >>> import sys; sys.setrecursionlimit(1000000)
   >>> A(3,10)
   8189
   >>> A2(3,10)
   8189
   >>> A(4,0)
   13
   >>> A(4,1)  # works on cs12, but not on my macbook
   65533

   Note: we need to lift the max recursive depth otherwise you can only test tiny m/n's.

   Extra Credit Questions:

   1. In your own words, explain why Ackermann is so much harder to compute than Fibonacci.

   2. Print the trace like this (for both cached and non-cached versions):

      A(2,1)
      A(1,A(2,0))
      A(1,A(1,1))
      A(1,A(0,A(1,0)))
      A(1,A(0,A(0,1)))
      A(1,A(0,2))
      A(1,3)
      A(0,A(1,2))
      A(0,A(0,A(1,1)))  cached: A(1,1) = 3
      A(0,A(0,3))
      A(0,4)
      A(2,1) = 5

      How much steps of computation could you save by memoization for A(3,5)?

   Filename: ackermann.py


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.

   >>> 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, []]]]]

   Hint: both search and insert should 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. (updates: both the path itself and its length are needed!)

   Based on the tree encoding in the above question, search for the longest path within a binary tree:

   >>> longest([[[[], 1, []], 2, [[], 3, []]], 4, [[[], 5, []], 6, [[], 7, [[], 9, []]]]])
   (5, [1, 2, 4, 6, 7, 9])

   which means the longest path has a length 5 edges: 1-2-4-6-7-9.
   
   In case of a tie, always choose the leftmost path (recursively defined).

   What's the time complexity of your algorithm?

   Filename: longest.py


4. 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!): --------------------------

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.