Exam (elaborations)
CS6515 Exam 2 QUESTIONS AND ANSWERS 2024
- Course
- Institution
CS6515 Exam 2 QUESTIONS AND ANSWERS 2024
[Show more]
Content preview
CS6515 Exam 2Basic Properties of Trees - ANSWERS-Tree's are undirected, connected and acyclic
that connect all nodes.
1. Tree on n vertices has (n-1) edges -> would have a cycle otherwise (more than
n-1 edges means cycle)
2. In tree exactly one path between every pair of vertices (otherwise it's not
connected)
- More than 1 path implies cycle
- less than 1 path implies not connected
3. Any connected G(V, E) with |E| = |V| - 1 is a tree
Kruskal's Algorithm - ANSWERS-1. Sort E by increasing weigt
2. Go through edges in order and add an edge to our current tree if it doesn't
create a cycle
Running Time: O(m log n), m = |E|, n = |V|
Is there ever a reason to use cycles in a flow graph? - ANSWERS-No
Flow Network Constraints: Capacity Constraint - ANSWERS-For all edges, the flow
must be larger than zero, but less than the capacity of that edge
,Goal of Flow Problem - ANSWERS-Maximize the flow out of the source (or into the
sink) of maximum size while satisfying the capacity and conservation of flow
constraints.
Flow Network Constraints: Conservation of Flow - ANSWERS-For all vertices (other
than the starting (source) and ending (sink) vertices), the flow into v must equal
the flow out of v.
Ford-Fulkerson Algo - ANSWERS-1. Start with f_e = 0 for all edges
2. Build the residual network for current flow
3. Find st-path in residual network
- if no such path then output f
4. Let c(p) = min(c_e - f_e); this is available capacity along some path
5. Augment f by c(p) along p
- for forward edges increase flow by c(p)
- for backward edge, decrease flow by c(p)
6. Repeat
Residual Network - ANSWERS-For flow network G = (V, E) with c_e for edges and
f_e for flows:
1. If there exists an edge vw where f_vw < c_vw, add vw to residual network with
capacity c_vw - f_aw
, 2. If there exists an edge vw where f_vw > 0, then add wv to residual network
with capacity f_vw
Note: 1 shows available forwards capacities and 2 shows residual backward
capacities.
Ford-Fulkerson Runtime - ANSWERS-Need to assume all capacities are integers.
This will allow flow to always increase by at least 1 unit per round. If C is the
maxflow, then there are at most C rounds. Each round of FF takes O(m), so the
total time is O(mC), which is pseudo-polynomial
What is the time to check whether or not a flow is a max flow - ANSWERS-- O(n +
m)
1. Build the residual graph takes O(n + m) time
2. Checking if there's a path from s to t using DFS, which takes linear time.
Capacity of a Cut - ANSWERS-Sum of capacities (edges) going from cut L to cut R
Max-flow = Min st-cut - ANSWERS-Size of Max-flow = min capacity of a st-cut
Cut Property: Key Ideas - ANSWERS-1. Take a tree T, add an edge e* will create a
cycle. Removing any edge of the cycle we'll get a new tree
2. A minimum weight edge across a cut is part of a MST
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Teacher101. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $16.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
83100 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now