Advanced Programming, Spring 2014
HW4 - Dynamic Programming II (intermediate)
Due electronically on Blackboard on Saturday April 26, 11:59pm.

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

Expected Amount of Work for an average student: 10-12 hours

References:

[1] CLRS Ch. 15.
    
    Sec. 15.2 (matrix-chain) and 15.5 (optimal BST, similar to matrix-chain)

[2] KT Ch. 6 (optional)
    http://www.aw-bc.com/info/kleinberg/assets/downloads/ch6.pdf
    
    Sec. 6.5 (RNA structure, which is similar to matrix-chain) 

[3] my tutorial slides on dynamic programming on graphs and hypergraphs:
    (only slides 14-15, 36-38, 45-48 are relevant)

    http://www.cis.upenn.edu/~lhuang3/COLING-tutorial-anim.pdf

[4] Catalan Numbers (optional):

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

1. Viterbi Algorithm and Topological Sort (see [3])

   Given a directed acyclic graph, count the number of paths 
   from the source node to the target node.

   The first line of the input file contains N, the number of graphs.
   Each graph has two lines: the first line has two integers, V (# of nodes) and E (# of edges).
   2 <= V <= 100;  1 <= E <= 1000. **We assume the graph is connected.**
   Nodes are numbered 1..V, with node 1 being the source node and node V being the target node.
   The second line is a list of edges (u, v), separated by a space.

   The output file has one line for each graph:
   If the graph is acyclic, output the number of paths from 1 to V.
   If the graph is cyclic, output "CYCLIC".

   input file example:
   	 2
	 5 6
	 (1, 2) (1, 3) (3, 2) (2, 5) (3, 5) (5, 4)
	 3 3
	 (1, 2) (2, 3) (3, 2)
	 
   output file example:
   	 3
	 CYCLIC
 
   filenames: viterbi_topdown.py and viterbi_bottomup.py
   
   Note: O(V+E).
   

2. Matrix-Chain Multiplication (see [1])

   the input file starts with N, the number of testcases,
   followed by N lines, each describing a testcase.
   
   the output file contains N lines, each line starts with 
   the optimal number of multiplications, followed by the optimal parenthesization.

   input file example:
   	 2
	 1x2 2x5 5x1
	 30x35 35x15 15x5 5x10 10x20 20x25
	 
   output file example:
   	 12 (A1(A2A3))
	 15125 ((A1(A2A3))((A4A5)A6))
  
   filenames: matrix_topdown.py and matrix_bottomup.py
   
   Note: O(n^3).


3. Longest Increasing Common Subsequence

   input file example:
   	 dab dacb 
	 zyx xyzx 
   output file example:
    	 ab
   	 z
   
   tiebreaking: do *not* worry about tiebreaking for this problem.
   any optimal solution is considered correct.

   filenames: lics.py (either recursive or bottom-up is fine)

   Note: O(n^3).


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

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

   filenames: lcs_w_subseq.py (either recursive or bottom-up is fine)

   Note: O(n^3).


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.