====================================================
Homework to be solved before Saturday, 25-June-2005
====================================================
  LeongHW; IOI-Training-2005, SoC, NUS


1. Work out the DP table for finding the length of the
   longest common subsequence for the following two strings:
     A = DBPAYLOG
     B = DEPLOYALG


2. The problem of finding a longest path in a DAG (directed
   acyclic graph) is solvable in polynomial time.

  (a) Give a fast (O(n+e)) algorithm for this problem -- your
      algorithm should be in pseudo-code.
      Trace out your algorithm for the sample graph with 
      the following list of weighted, directed edges:

         (A,C,3), (B,D,5), (B,E,8), (C,E,6), (C,F,9), 
         (D,F,2), (D,G,7), (E,H,4), (F,H,1), (G,H,10)

  (b) Give a DP formulation of your algorithm.

  (c) Look back and try to think about the 5 steps in applying
      the DP approach that I have listed during lectures.

3. Solve Problem 10003 "Cutting Sticks" problem on our online 
   judging system. Deadline: Saturday 10:00am
   (Problem statement should be online.)



------------------------------
Steps in Applying DP Method
------------------------------
  LeongHW (June 2005)

1. Understand the Problem
     and the parameters;

2. Generalize the Problem

3. Define the "correct" problem
     - uses all the parameters
     - the solution is a "special case"
     - make use of history

4. Find a recursive solution (algorithm)

5. Extract the DP solution

--------------------------------