Problem Set 8 Solution

(10 pts) Ginerva Weasley is playing with the network given below. Help her calculate the number of paths from node 1 to node 14.



Hint: assume a \path" must have at least one edge in it to be well de ned, and use dynamic programming to ll in a table that counts number of paths from each node j to 14, starting from 14 down to 1.




1


/2


/3


/4




/5








/6




































!












7


/8


/9


/10






/11












































!




!




















12






/13


/14


































(10 pts) Ginny Weasley needs your help with her wizardly homework. She’s trying to come up with an example of a directed graph G = (V; E), a start vertex v 2 V and a set of tree edges ET E such that for each vertex v 2 V , the unique path in the graph (V; ET ) from s to v is a shortest path in G, yet the set of edges ET cannot be produced by running a depth- rst search on G, no matter how the vertices are ordered in each adjacency list. Include an explanation of why your example satis es the requirements.






(15 pts) Prof. Dumbledore needs your help to compute the in- and out-degrees of all vertices in a directed multigraph G. However, he is not sure how to represent the graph so that the calculation is most e cient. For each of the three possible represen-tations, express your answers in asymptotic notation (the only notation Dumbledore understands), in terms of V and E, and justify your claim.



An adjacency matrix representation. Assume the size of the matrix is known.



An edge list representation. Assume vertices have arbitrary labels.



An adjacency list representation. Assume the vector’s length is known.



(30 pts) Deep in the heart of the Hogwarts School of Witchcraft and Wizardry, there lies a magical grey parrot that demands that any challenger e ciently convert directed multigraphs into directed simple graphs. If the wizard can correctly solve a series of arbitrary instances of this problem, the parrot will unlock a secret passageway.



Let G = (E; V ) denote a directed multigraph. A directed simple graph is a G0 = (V; E0 ), such that E0 is derived from the edges in E so that (i) every directed multi-edge, e.g., f(u; v); (u; v)g or even simply f(u; v)g, has been replaced by a single directed




1



CSCI 3104
Profs. Clauset & Grochow
Problem Set 8
CU-Boulder












input
G = (V,E)


output
G′ = (V, E′)
1
2
3
1
2
3


5
4


5
4















1
3
2






1
2
3


2
1
3
3
3


2
1
3


3
4








3
4




4
4
5
2
5
1
4
1
2
5
5
3
1






5
1
3

























An example of transforming G ! G0










edge f(u; v)g and (ii) all self-loops (u; u) have been removed.







Describe and analyze an algorithm (explain how it works, give pseudocode if neces-sary, derive its running time and space usage, and prove its correctness) that takes O(V + E) time and space to convert G into G0 , and thereby will solve any of the Sphinx’s questions. Assume both G and G0 are stored as adjacency lists.




Hermione’s hints: Don’t assume adjacencies Adj[u] are ordered in any particular way, and remember that you can add edges to the list and then remove ones you don’t need.







(15 pts extra credit) Professor McGonagall has provided the young wizard Ron with three magical batteries whose sizes are 42, 27, and 16 morts, respectively. (A mort is a unit of wizard energy.) The 27-mort and 16-mort batteries are fully charged (containing 27 and 16 morts of energy, respectively), while the 42-mort battery is empty, with 0 morts. McGonagall says that Ron is only allowed to use, repeatedly, if necessary, the mort transfer spell when working with these batteries. This spell transfers all the morts in one battery to another battery, and it halts the transfer either when the source battery has no morts remaining or when the destination battery is fully charged (whichever comes rst).






2



CSCI 3104
Profs. Clauset & Grochow
Problem Set 8
CU-Boulder










McGonagall challenges Ron to determine whether there exists a sequence of mort-transfer spells that leaves exactly 12 morts either in the 27-mort or in the 16-mort battery.




Ron knows this is actually a graph problem. Give a precise de nition of how to model this problem as a graph, and state the speci c question about this graph that must be answered.



What algorithm should Ron apply to solve the graph problem?



Apply that algorithm to McGonagall’s question. Report and justify your answer.

































































































































3