Advanced Programming, Spring 2014
HW3 - Dynamic Programming I (simple)
Due electronically on Blackboard on Saturday March 29, 11:59pm (except for the extra credit problems).

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

Expected Amount of Work for an average student: 8-10 hours (excluding extra credit problems).

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

    (0-1 Knapsack, a.k.a. "subset sum", is covered in Section 6.4)
[3] KMP (string matching):
    CLRS Ch. 32.4
    http://www.cse.ust.hk/~dekai/271/notes/L16/L16.ps

1. Bounded Knapsack

   You have n items, each with weight w_i, value v_i, and copies c_i.
   What's the best value for a bag of W?

   input format: 
   	 the first line contains two integers, n and W.
	 the next n lines each contains three integers: w_i, v_i, and c_i.
   output format:
   	 the first line contains the best value for W.
	 the second line has n numbers j_i, meaning you're taking j_i copies of item i.
   
   input file example:
   	 2 3
	 2 4 2
	 3 5 3
   output file example:
    	 5
	 0 1

   tie-breaking: lexicalgraphical: i.e., 0 1 is better than 1 0.
   (in other words, taking 0 copies of item 1 and 1 copy of item 2 is better 
    than taking 1 copy of item 1 and 0 copies of item 2.)

   filenames: knapsack.py (top-down) and knapsack2.py (bottom-up)

   Questions:
   1. When is top-down much faster than bottom-up?
      give me an instance where top-down is 5 times faster than bottom-up.
      (you need to provide the input, output, running times, 
      and number of non-zero cells in opt in each of the two approaches).

   2. When is bottom-up much faster than top-down?
      give me an instance where bottom-up is 5 times faster.

   3. Would your top-down or bottom-up work if the weights are float numbers?
      if not, how would you adapt them to float numbers?

2. Longest (Strictly-) Increasing Subsequence
   
   input file contains several lines, each with a lowercase string
   output file contains the same number of lines, each with its LIS.

   input file example:
   	 aebbcg
	 zyx
   output file example:
    	 abcg         
   	 z

   tiebreaking: do *not* worry about tiebreaking for this problem.
   any optimal solution is considered correct.
   i.e., for the second line, z or y or x are all correct.

   filenames: lis.py (top-down) and lis2.py (bottom-up)

3. Longest Common Subsequence

   input file contains several lines, each with a pair of lowercase strings
   output file contains the same number of lines, each with its LCS.

   if the LCS is empty, print "NO LCS"
   
   input file example:
   	 abcbdab bdcaba
	 zzz x
   output file example:
    	 bcba
   	 NO LCS

   tiebreaking: do *not* worry about tiebreaking for this problem.
   any optimal solution is considered correct.

   filename: lcs.py (top-down) and lcs2.py (bottom-up)

   Questions:
   1. When is top-down much faster than bottom-up?
      give me an instance where top-down is 5 times faster than bottom-up.
      (you need to provide the input, output, running times, 
      and number of non-zero cells in opt in each of the two approaches).

   2. When is bottom-up much faster than top-down?
      give me an instance where bottom-up is 5 times faster.


Extra Credit Problems: --------------------------------

This part is due by Wednesday Apr 2 via email to both the instructor and the TA.

4. LCS without a query string as a *subsequence*.

   input file example:
   	 abcbdab bdcaba bca
	 zzz zz z
   output file example:
    	 bdab
   	 NO LCS
   
   tiebreaking: do *not* worry about tiebreaking for this problem.
   any optimal solution is considered correct.

   filenames: lcs_wo_subseq.py (top-down) and lcs_wo_subseq2.py (bottom-up)

5. codeforces 346-B. LCS w/o a query string as *substring*.

   hint: LCS + KMP (or automaton).
   use the state in the KMP automaton for the 3rd dimension (the k in opt[i][j][k]).

   Filename: lucky.py (either top-down or bottom-up is fine)

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. 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.