CS 519-005, Algorithms (MS/MEng-level), Fall 2016
HW5 - DP (part 1: simple)

HWs 5-7 are all on DPs.

Due electronically on Canvas on Sunday Oct 23, 11:59pm.
No late submission will be accepted.

Include in your submission: report.txt, mis.py, bsts.py, bitstrings.py.
DO _NOT_ ZIP YOUR SUBMISSION.
mis.py will be graded for correctness (1%).

Textbooks for References:
[1] CLRS Ch. 15
[2] KT Ch. 6, freely available online (strongly recommended!):
    http://www.aw-bc.com/info/kleinberg/assets/downloads/ch6.pdf

[UPDATE] hint: among the three coding questions, p3 is the easiest, and p1 is similar to p3.
	 you'll realize that both are very similar to p0 (fibonacci).
	 p2 is slightly different from these, but also very easy.

0. Compare two recursive implementations of fib (naive vs. memoized).
   (a) What's exact complexity of naive in theory?
   (b) Let's say you know it's O(a^n); can you curve-fit to determine the approximate value of a?
   (c) Does this value match the theoretical complexity?

   NO NEED to submit fib.py, but include your answers to the above questions in report.txt.
   Hint: for (b), you can use n = 5..35, and use gnuplot (you can "set logscale y").

   or in detail:

   $ python fib.py > fib.txt
   $ gnuplot

   plot "fib.txt" u 1:2 w lp
   set logscale y; replot

   f(x) = a*x + b
   fit f(x) "fib.txt" using 1:(log($2)) via a,b

   [UPDATE] hint: here's the memoized code; note this "cache=None" trick -- you'll need that trick
   	    to ensure a correct answer in problems 1-3.

            def fib2(n, cache=None):
                if cache is None:
                    cache = {}
                if n in cache:
                    return cache[n]
                print "calculating", n
                cache[n] = 1 if n <= 2 else fib2(n-1, cache) + fib2(n-2, cache)
                return cache[n]
	    

1. [WILL BE GRADED]
   Maximum Weighted Independent Set 

   [UPDATE] hint: independent set is a set where no two numbers are neighbors in the original list.
   	    see also https://en.wikipedia.org/wiki/Independent_set_(graph_theory)

   input:  a list of numbers (could be negative)
   output: a pair of the max sum and the list of numbers chosen

   >>> max_wis([7,8,5])
   (12, [7,5])

   >>> max_wis([-1,8,10])
   (10, [10])

   >>> max_wis([])
   (0, [])

   [UPDATE] hint: if all numbers are negative, the optimal solution is 0,
            since [] is an independent set according to the definition above.

   >>> max_wis([-5, -1, -4])
   (0, [])

   What's the complexity?
   
   Include both top-down (max_wis()) and bottom-up (max_wis2()) solutions, 
   and make sure they produce exact same results. We'll only grade the top-down version.

   Tie-breaking: any best solution is considered correct.

   Filename: mis.py

   [UPDATE] hint: you can also use the naive O(2^n) exhaustive search method to verify your answer.
   

2. Number of n-node BSTs

   input: n
   output: number of n-node BSTs

   >>> bsts(2)
   2
   >>> bsts(3)
   5
   >>> bsts(5)
   42

   [UPDATE] hint: there are two 2-node BSTs:
      2    1
     /      \
    1        2
   Note that all other 2-node BSTs are *isomorphic* to either one.
      
   What's the complexity of this DP?
   
   What's the name of this famous number series?

   Feel free to use any implementation style.
   
   Filename: bsts.py

3. Number of bit strings of length n that has

   1) no two consecutive 0s.
   2) two consecutive 0s.
   
   >>> num_no(3)
   5
   >>> num_yes(3)
   3

   [UPDATE] hint: there are three 3-bit 0/1-strings that have two consecutive 0s.
            001  100  000
            The other five 3-bit 0/1-strings have no two consecutive 0s:
	    010  011  101  110  111

   Feel free to choose any implementation style.

   Filename: bitstrings.py

   [UPDATE] hint: like problem 1, you can also use the O(2^n) exhaustive search method to verify your answer.


Debriefing (required!): --------------------------

0. What's your name?
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. Which part(s) of the course you like the most so far?
6. Which part(s) of the course you dislike the most so far?

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.