A Level Further Mathematics A Y544/01 Discrete Mathematics Mark Scheme - Autumn 2021

$ 5.5

University of California, Los Angeles LIFESCIENC 30A. Midterm1 Solutions.

$ 13

WGU C207 OA Questions and Answers with Complete Solutions

$ 15

Cyber Awareness 2022 Knowledge Check Already Passed

$ 6

Cambridge IGCSE: PHYSICS Paper 6 Alternative to Practical QUESTION PAPER - March 2022

$ 5.5

eBook [PDF] Nonlinear Dynamics and Chaos 1st Edition By Steven H. Strogatz

$ 20

eBook Biomechanics of Human Communication Neurophysiology, Regulation, and Systems Thinking 1st Edition By S. Faye Molicki

$ 30

Pearson Edexcel GCE In Economics B (9EB0) Paper 2: Competing in the Global Economy Mark Scheme (Results) November 2021

$ 7.5

AAPC CPC FINAL EXAM UPDATED 2025 WITH QUESTIONS AND 100% CORRECT ANSWERS GUARANTEED A+

$ 19

CNA Chapter 7 Quiz (Answered) Verified Answers 100% 2023

$ 5

Homework 1 - Solution

$ 7

Solution Manual for Database Systems, The Complete Book, 2e Hector Garcia-Molina, Jeffrey Ullman, Jennifer Widom

$ 23

Certiport Cybersecurity Certification / 2024 Exam Prep / ITS-303 Practice Tests / Pass Guaranteed

$ 15.5

WGU D220 Questions and Answers Already Passed

$ 10

University of the People MATH 1201 College Algebra - Term 3 Final Exam -Proctored.

$ 8

WGU C464 - Introduction to Communication Questions and Answers Already Passed

$ 10

Yoost & Crawford: Fundamentals of Nursing: Active Learning for Collaborative Practice, 2nd Edition Review Questions

$ 8

Sophia - College Algebra - Milestone Study Guide Revisions, 16 Updated Study Guide, Correctly Answered Questions, Test bank Questions and Answers with Explanations (latest Update), 100% Correct, Download to Score A

$ 30

eBook [PDF] Public Health An Introduction to the Science and Practice of Population Health 1st Edition By James Shultz, Lisa Sullivan, Sandro Galea

$ 30

Computer Science > QUESTIONS & ANSWERS > CS 573: Algorithms, Fall 2013 Homework 3: Solutions (All)

CS 573: Algorithms, Fall 2013 Homework 3: Solutions

Document Content and Description Below

CS 573: Algorithms, Fall 2013 Homework 3: Solutions Version 1.0 1. Prove infeasibility. (25 pts.) You are trying to solve a circulation problem, but it is not feasible. The problem has demands, but no capacity limits on the edges. More formally, there is a graph G = (V, E), and demands dv for each node v (satisfying ∑v∈V dv = 0), and the problem is to decide if there is a flow f such that f(e) ≥ 0 and fin(v) − fout(v) = dv for all nodes v ∈ V . Note that this problem can be solved via the circulation algorithm from Section 7.7 by setting ce = +∞ for all edges e ∈ E. (Alternately, it is enough to set ce to be an extremely large number for each edge – say, larger than the total of all positive demands dv in the graph.) You want to fix up the graph to make the problem feasible, so it would be very useful to know why the problem is not feasible as it stands now. On a closer look, you see that there is a subset U of nodes such that there is no edge into U, and yet ∑v∈U dv > 0. You quickly realize that the existence of such a set immediately implies that the flow cannot exist: The set U has a positive total demand, and so needs incoming flow, and yet U has no edges into it. In trying to evaluate how far the problem is from being solvable, you wonder how big the demand of a set with no incoming edges can be. Give a polynomial-time algorithm to find a subset S ⊂ V of nodes such that there is no edge into S and for which ∑v∈S dv is as large as possible subject to this condition. Solution: Compute the strong connected components of G – this can be done in linear time. Collapse every connected component into a single super vertex. Let H be the resulting graph. The demand of a vertex v in H is the total sum of the demands of the vertices of G collapsed into v. The graph H is no a directed acyclic graph, and the project selection algorithm can be applied to H and compute the desired set. As for how to compute the strong connected components – one can just repeatedly find a cycle in the graph, and collapse it repeatedly. Finding a cycle can be done by doing a single DFS in the graph – fill up your education if you do not know the details - this is an easy exam question

[Show More]

Last updated: 3 years ago

Preview 1 out of 4 pages

Buy Now

Instant download

We Accept: