CAS CS 330 Study Guide - Final Guide: Bipartite Graph, Maximum Flow Problem, Minimum Cut

• School: Boston University
• Department: Computer Science
• Course: CAS CS 330
• Professor: John Byers

Document Summary

Input: n, w1, ,wn, v1, ,vn for w = 0 to w. M[0, w] = 0 for i = 1 to n for w = 1 to w if (wi > w) M[i, w] = max {m[i-1, w], vi + m[i-1, w-wi ]} return m[n, w] Breaking a sub problem into smaller sub problems to solve one large problem. Store results of each subproblem in a cache and look up the results as needed to solve the bigger subproblem. Sort jobs by finish times so that f1 f2 fn. Compute p(1), p(2), , p(n) for j = 1 to n. M[j] = max(wj + m-compute-opt(p(j)), m-compute-opt(j-1)) return m[j] } Sequence-alignment(m, n, x1x2xm, y1y2yn, , ) for i = 0 to m. M[0, i] = i for j = 0 to n. M[j, 0] = j for i = 1 to m for j = 1 to n.