#sequence alignment

Ÿ   Interval Scheduling(Binary Choice)

-       Greedy can be used if all weights are 1

-       Sort by finishing time: O(nlogn)

-       Computing: O(n) –if Memoization used

-       OPT(j) = 0(if j=2) / otherwise max {vj + Opt(p(j)), OPT(j-1)}

Ÿ   Segmented Least Squares(Multi-way choice)

-       O(n^3) – can be improved to O(n^2) by pre-computing various statistics

-       OPT(j) = 0 if j=0 / min {e(i,j) + c + OPT(i-1)} if 1<=i<=j

-       OPT(j): minimum cost for points / e(i,j): minimum sum of squares for points

Ÿ   Knapsack(Adding a new variable)

-       OPT(i, w) = 0 if i=0 / OPT(i-1, w) if wi > w / max {OPT(i-1, w) + OPT(i-1,w-wi)}

-       O(nW) – not polynomial in input size(Pseudo-polynomial)

-       NP-complete

Ÿ   Sequence Alignment

-       Gap penalty ;(delta) mismatch penalty (alpha)

-       OPT(i,j) = jd if i=0 / min(axiyi + OPT(i-1, j-1), d + OPT(i-1, j), d + OPT(i, j-1) / id if j=0