Study Guides (248,414)
United States (123,350)

CAS CS 330 Final: CS330 Final Notes

9 Pages
Unlock Document

Computer Science
CAS CS 330
John Byers

★ Dynamic Programming  ○ 2 way choice ○ Knapsack Algorithm : 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] = M[i-1, w] else M[i, w] = max {M[i-1, w], vi + M[i-1, w-wi ]} return M[n, W] Time Complexity: O(nW) ○ Recursion ■ Breaking a sub problem into smaller sub problems to solve one large problem. ○ Memoization ■ Store results of each subproblem in a cache and look up the results as needed to solve the bigger subproblem ○ Weighted interval scheduling Algorithm: Input: n, s1,…,sn , f1,…,fn , v1,…,vn Sort jobs by finish times so that f1 ≤ f2 ≤ ... ≤ fn. Compute p(1), p(2), …, p(n) for j = 1 to n M[j] = empty M[j] = 0 M-Compute-Opt(j) { if (M[j] is empty) M[j] = max(wj + M-Compute-Opt(p(j)), M-Compute-Opt(j-1)) return M[j] } Time Complexity: O(n log n) ○ Segmented least squares ○ Sequence alignment Algorithm: Sequence-Alignment(m, n, x1x2...xm, y1y2...yn, δ, α) 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 M[i, j] = min(α[xi, yj] + M[i-1, j-1], δ + M[i-1, j], δ + M[i, j-1]) return M[m, n] } Time Complexity: O(mn) ○ Subset sum ■ ○ Bellman ford Algorithm: Push-Based-Shortest-Path(G, s, t) { foreach node v ∈ V { M[v] ← ∞ successor[v] ← φ } M[t] = 0 for i = 1 to n-1 { foreach node w ∈ V { if (M[w] has been updated in previous iteration) { foreach node v such that (v, w) ∈ E { if (M[v] > M[w] + cvw) { M[v] ← M[w] + cvw successor[v] ← w } } } If no M[w] value changed in iteration i, stop. } } Time Complexity: O(mn) ○ The three things of dynamic ■ Binary choice- Weighted Interval Scheduling ■ Multiway choice- Segmented least squares ■ Adding a new variable- knapsack ■ Over intervals- sequence alignment ★ Flow  ○ Residual graph: ■ What is left over. ○ max-flow/min cut ■ Mincut Max flow capacity you should get ○ Weak duality ■ The flow is at most the capacity of the min cut. ○ Definition of flows ○ Ford fulkerson ○ Bipartite matching ■ Take bipartite graph add source node and sink node ■ Make all the edges directed towards the sink node ■ Set each edge weight to 1 ■ Run ford fulkerson ■ The max flow of the graph == # perfect matchings ○ Marriage theorem ■ There is a perfect matching if the size of one set of the nodes >= the other set of nodes ■ Perfect matching= one-to-one matching, only one node from one side of the bipartite graph can match to one on the other side ○ Disjoint paths ■ No shared edges. ■ Make edge directed ■ Set each edge weight to 1 ■ Run ford faulkerson ■ Max flow is number of disjoint edge paths. ○ Circulation(Supply and Demand) ■ Donor Blood Problem From Lab ■ Supply and Demand as edge weights, middle edge weights set to infinity ■ Run ford fulkerson to see if the demand can be met with the supply ★ Complexity (NP stuff)  ○ polynomial time reduction To establish NP completeness of problem Y ■ Step 1. Show that Y is in NP. (Certificate, say a portion of the problem can be solved in polynomial time) ■ Step 2. Choose an NP-complete problem X. ■ Step 3. Prove that X ≤ p Y ***Claim iff ○ P vs. NP vs NP vs NP Hard vs NP Complete definition ■ P:​P is a complexity class that represents the set of all decision problems that can be solved in polynomial time​. That is, given an instance of the problem, the answer yes or no can be decided in polynomial time. ■ NP: ​NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. This means that if someone gives us an instance of the problem and a certificate (sometimes called a witness) to the answer being yes, we can check that it is correct in polynomial time. NP Complete:​ ​NP-Complete is a complexity class which represents the set of all problems ​ X​in NP for which it is possible to reduce any other NP problem ​ Y​to X​in polynomial time. Intuitively this means that we can solve ​ Y​quickly if we know how to solve ​X​quickly. Precisely, ​Y​is reducible to X​, if there is a polynomial time algorithm ​ f​to
More Less

Related notes for CAS CS 330

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.