false

Study Guides
(248,414)

United States
(123,350)

Boston University
(4,489)

Computer Science
(38)

CAS CS 330
(3)

John Byers
(3)

Final

Unlock Document

Computer Science

CAS CS 330

John Byers

Spring

Description

★ 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
■ https://www.youtube.com/watch?v=s6FhG--P7z0
○ 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 Xin NP for which it is possible to reduce any
other NP problem Yto Xin polynomial time.
Intuitively this means that we can solve Yquickly if we know how to
solve Xquickly. Precisely, Yis reducible to X, if there is a polynomial
time algorithm fto

More
Less
Related notes for CAS CS 330

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.