Exam (elaborations)
CS6515 Exam 2 Questions And Complete Solutions
- Course
- Institution
CS6515 Exam 2 Questions And Complete Solutions
[Show more]
Content preview
CS6515 Exam 2 Questions AndComplete Solutions
Basic Properties of Trees CORRECT 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 CORRECT 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? CORRECT ANSWERS No
Flow Network Constraints: Capacity Constraint CORRECT ANSWERS For all edges, the flow must be larger than zero, but less than the capacity of that edge
Goal of Flow Problem CORRECT 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 CORRECT 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 CORRECT 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 CORRECT 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 CORRECT 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 CORRECT 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 CORRECT ANSWERS Sum of capacities (edges) going from cut L to cut R
Max-flow = Min st-cut CORRECT ANSWERS Size of Max-flow = min capacity of a st-
cut
Cut Property: Key Ideas CORRECT 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
Runtime: Confirm a vertex exists CORRECT ANSWERS O(1)
Runtime: Confirm edge exists CORRECT ANSWERS O(m)
Runtime: Explore entire graph CORRECT ANSWERS O(n + m)
x mod N = CORRECT ANSWERS x = qN + r
Basic Properties of MOD CORRECT ANSWERS if x:::y MOD N & a:::b MOD N:
1. x+a ::: y+b MOD N
2. xa ::: yb MODN N
Time to multiply or divide 2 n-bit numbers CORRECT ANSWERS O(n^2)
Modular Inverse CORRECT ANSWERS X is the multiplicative inverse of Z MOD N if:
- (x * z) MOD N = 1
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 ElevatedExcellence. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $12.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
75632 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now