Alpha Geek

(8)

$10/per page/Negotiable

About Alpha Geek

Levels Tought:
University

Expertise:
Accounting,Algebra See all
Accounting,Algebra,Architecture and Design,Art & Design,Biology,Business & Finance,Calculus,Chemistry,Communications,Computer Science,Environmental science,Essay writing,Programming,Social Science,Statistics Hide all
Teaching Since: Apr 2017
Last Sign in: 439 Weeks Ago
Questions Answered: 9562
Tutorials Posted: 9559

Education

  • bachelor in business administration
    Polytechnic State University Sanluis
    Jan-2006 - Nov-2010

  • CPA
    Polytechnic State University
    Jan-2012 - Nov-2016

Experience

  • Professor
    Harvard Square Academy (HS2)
    Mar-2012 - Present

Category > Business & Finance Posted 28 Apr 2017 My Price 3.00

Give a linear-time algorithm that takes

Give a linear-time algorithm that takes as input a directed acyclic graph G = (V, E) and two vertices s and t, and returns the number of paths from s to t in G. For example, in the directed acyclic graph of Figure 22.8, there are exactly four paths from vertex p to vertex v: pov, por yv, posr yv, and psr yv. (Your algorithm only needs to count the paths, not list them.) Answer Add a field to the vertex representation to hold an integer count. Initially, set vertex t’s count to 1 and other vertices’ count to 0. Start running DFS with s as the start vertex. When t is discovered, it should be immediately marked as finished (BLACK), without further processing starting from it. Subsequently, each time DFS finishes a vertex v, set v’s count to the sum of the counts of all vertices adjacent to v. When DFS finishes vertex s, stop and return the count computed for s. Topological sort + dynamic programming

 

 

Answers

Alpha Geek
(8)
Status NEW Posted 28 Apr 2017 12:04 PM My Price 3.00

-----------

Attachments

file 1493381309-Answer.docx preview (218 words )
G-----------ive----------- a -----------lin-----------ear------------ti-----------me -----------alg-----------ori-----------thm----------- th-----------at -----------tak-----------es -----------as -----------inp-----------ut -----------a d-----------ire-----------cte-----------d a-----------cyc-----------lic----------- gr-----------aph----------- G -----------= (-----------V, -----------E) -----------and----------- tw-----------o v-----------ert-----------ice-----------s s----------- an-----------d t-----------, a-----------nd -----------ret-----------urn-----------s t-----------he -----------num-----------ber----------- of----------- pa-----------ths----------- fr-----------om -----------s t-----------o t----------- in----------- G.----------- Fo-----------r e-----------xam-----------ple-----------, i-----------n t-----------he -----------dir-----------ect-----------ed -----------acy-----------cli-----------c g-----------rap-----------h o-----------f F-----------igu-----------re -----------22.-----------8, -----------the-----------re -----------are----------- ex-----------act-----------ly -----------fou-----------r p-----------ath-----------s f-----------rom----------- ve-----------rte-----------x p----------- to----------- ve-----------rte-----------x v-----------: p-----------ov,----------- po-----------r y-----------v, -----------pos-----------r y-----------v, -----------and----------- ps-----------r y-----------v. -----------(Yo-----------ur -----------alg-----------ori-----------thm----------- on-----------ly -----------nee-----------ds -----------to -----------cou-----------nt -----------the----------- pa-----------ths-----------, n-----------ot -----------lis-----------t t-----------hem-----------.) -----------Ans-----------wer----------- Ad-----------d a----------- fi-----------eld----------- to----------- th-----------e v-----------ert-----------ex -----------rep-----------res-----------ent-----------ati-----------on -----------to -----------hol-----------d
Not Rated(0)
Relevent Questions