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 limit ...

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: 2 months ago

Preview 1 out of 4 pages

Instant download after payment

Card Payments

₿ Crypto Accepted

Instant download

Preview of CS 573: Algorithms, Fall 2013 Homework 3: Solutions

Buy this document to get the full access instantly

Instant Download Access after purchase

Instant download after payment

Card Payments

₿ Crypto Accepted

Report Copyright Violation

Reviews( 0 )

QUESTIONS & ANSWERS ?

$8.00

Instant download after payment

Card Payments

₿ Crypto Accepted

88

0

Document information

Connected school, study & course

About the document

Uploaded On

May 21, 2021

Number of pages

4

Written in

All

QUESTIONS & ANSWERS

Seller

Cheryshev

Member since 5 years

102 Documents Sold

Reviews Received

6

4

1

0

1

Additional information

This document has been written for:

Computer Science

QUESTIONS & ANSWERS

Uploaded

May 21, 2021

Downloads

0

Views

88

Document Keyword Tags

Recommended For You

Get more on QUESTIONS & ANSWERS »

Preview of CS 573: Algorithms, Fall 2013 Homework 3: Solutions Version 1.0

Same Course Code Popular Match

$5

4 Pages

CS 573: Algorithms, Fall 2013 Homework 3: Solutions Version 1....

Jun 09, 2026

Related document

Preview of CS 573: Algorithms, Fall 2013

Same Course Code Popular Match

$10

5 Pages

CS 573: Algorithms, Fall 2013

Nov 16, 2022

Preview of eBook for Concepts of Programming Languages 12th Edition By Robert W. Sebesta

Same Course Popular Match

$20

784 Pages

eBook for Concepts of Programming Languages 12th Edition By R...

May 15, 2026

Related document

Preview of Introduction to Programming with Java A Problem Solving Approach 2nd Edition By John Dean

Same Course Popular Match

$20

728 Pages

Introduction to Programming with Java A Problem Solving Approa...

Apr 26, 2026

Related document

Preview of Introduction to JavaScript Programming with XML and PHP 1st Edition By Elizabeth Drake (S

Same Course Popular Match

$22

18 Pages

Introduction to JavaScript Programming with XML and PHP 1st Ed...

Apr 26, 2026

Related document

Preview of Computer Systems Application 1st Edition By Viktor Boradin eBook PDF

Same Course

$25

277 Pages

Computer Systems Application 1st Edition By Viktor Boradin eBo...

May 15, 2026

Related document

Preview of [eBook] [PDF] computer systems application By Viktor Boradin

Same Course

$25

277 Pages

[eBook] [PDF] computer systems application By Viktor Boradin

May 15, 2026

Related document

Preview of eBook PDF for Computing Legacies Digital Cultures Of Simulation 1st Edition By Peter Krapp

Same Course

$13

229 Pages

eBook PDF for Computing Legacies Digital Cultures Of Simulatio...

May 12, 2026

Related document

Preview of Using AI in Marketing An Introduction By Greg Kihlström PDF ebook

Same Course

$25

159 Pages

Using AI in Marketing An Introduction By Greg Kihlström PDF eb...

May 06, 2026

Related document

Preview of The AI Marketing Playbook Concepts Methods Applications 2nd Edition By Mark Lamplugh PDF e

Same Course

$25

296 Pages

The AI Marketing Playbook Concepts Methods Applications 2nd Ed...

May 06, 2026

Related document

Preview of Solutions Manual for Essentials of Symbolic Logic 3rd Edition by R.L. Simpson

Same Course

$14

120 Pages

Solutions Manual for Essentials of Symbolic Logic 3rd Edition...

Apr 28, 2026

Related document

Preview of WGU C851 LINUX FOUNDATIONS COMPUTER NEWEST 2026/2027 ALL STUDY QUESTIONS WITH VERIFIED SOL

Same Course

$15.5

24 Pages

WGU C851 LINUX FOUNDATIONS COMPUTER NEWEST 2026/2027 ALL STUDY...

May 13, 2026

Related document

Preview of WGU C952 COMPUTER ARCHITECTURE LATEST COMPUTER SCIENCE 2026/2027 ALL STUDY QUESTIONS WITH

Same Course

$10

7 Pages

WGU C952 COMPUTER ARCHITECTURE LATEST COMPUTER SCIENCE 2026/20...

May 13, 2026

Related document

Preview of FEMA Final Exam ICS 100 (IS-100.C) Introduction to the Incident Command System

Same Course Popular Match

$13

29 Pages

FEMA Final Exam ICS 100 (IS-100.C) Introduction to the Inciden...

May 11, 2026

Related document

Preview of NREMT FINAL EXAM TEST BANK LATEST 2024-2025 / EMT Cognitive Exam 370 Questions / Score 100

Same Category

$9

10 Pages

NREMT FINAL EXAM TEST BANK LATEST 2024-2025 / EMT Cognitive Ex...

May 15, 2026

Related document

Preview of Derm Test Bank / Score 100% / Updated 2026 Dermatology Practice Questions & Exam Review

Same Category

$9

7 Pages

Derm Test Bank / Score 100% / Updated 2026 Dermatology Practic...

May 14, 2026

Related document

Preview of Skin Test Bank 23 & 24 / Score 100% / Updated 2026 Dermatology Practice Questions & Exam R

Same Category

$10

8 Pages

Skin Test Bank 23 & 24 / Score 100% / Updated 2026 Dermatology...

May 14, 2026

Related document

Preview of ` NU 665 final EXAM LATEST TESTBANK 2025 UPDATE WITH COMPLETE QUESTIONS AND CORRECTLY WE

Same Category

$14

272 Pages

` NU 665 final EXAM LATEST TESTBANK 2025 UPDATE WITH COMPLETE...

May 14, 2026

Related document

Preview of [eTextbook] [PDF] CompTIA Network+ Guide to Networks 9th edition By Jill West

Same Course Popular Match

$29

835 Pages

[eTextbook] [PDF] CompTIA Network+ Guide to Networks 9th editi...

Apr 28, 2026

Related document

Preview of GMetrix Premiere Pro Terminology / Score 100% / New Version 2025 Update / Certification Ex

Same Category

$18

9 Pages

GMetrix Premiere Pro Terminology / Score 100% / New Version 20...

May 15, 2026

Related document

More related documents below

Browse more QUESTIONS & ANSWERS

More From Cheryshev

View all Cheryshev's documents »

$8.00

Instant download after payment

Card Payments

₿ Crypto Accepted

What is Scholarfriends

Scholarfriends.com Online Platform by Browsegrades Inc. 651N South Broad St, Middletown DE. United States.

Get to know us

About Us
Privacy Statement
Refund Policy
Terms and Conditions
Contact Us
Blog
HTML Sitemap
Sellers Directory (A–Z)

We are here to help

We're available through e-mail, Twitter, and live chat.
FAQ
Questions? Leave a message!

Follow us on

Instagram
Linktree
X (Twitter)

Useful links

Join our Subreddit

Solutions Manuals for Accounting, Business, Economics and Management Text Books. The Popular and the Latest.

Popular NURSING Test Banks

Sellers Directory (A–Z)

We accept

payment cards

Copyright © Scholarfriends · High quality services·