Week 7 Assignment 7 (02,03 April)

link

1. See the graph from lecture and the text format HW_07_Graph. Implement a random walk procedure by following nodes based on their assigned probabilities. In simple graph like this you can implement it in any manner. For a more general case, you can use adjacency lists with probability attached to all edges from a vertex. Generate random value between 0..1. Choose edge such that the generated probability is less than the sum of edge probabilities so far. Edges: 0.1, 0.3, 0.4, 0.2; random=0.576 => 0.576 > 0.1; 0.576 > 0.4 ; 0.576 < 0.8 => choose link nr 3.

2. Simulate this 100, 1000, ... 100,000 times. Count how often you visit each state; Output frequencies. And turn the frequencies into probabilities (that sum up to 1).

3. Use the same graph as a matrix with transition probabilities from state to state (A=0, B=1, .. E=4).

Matrix: M = 
	0	0.95	0.05	0	0
	0	0	0	0.7	0.3
	0	0	0	0	1.0
	1.0	0	0	0	0
	0.8	0	0	0.2	0

Use matrix multiplication and calculate powers of M. I.e. M2=M*M, M10, M100, M1000. Print out the whole matrix. What do you observe after repeatedly calculating powers? Here you can choose to implement it in any programming language. Alternatively, Matlab, R, Maple, etc mathematical packages can be used. (For more explanations you can read slides in here.)

4. Simulate the operations (add: 25 10 9 2 17 5 ; delete min, delete min, add 16 14 ; decrease value 17->1 , 9->1 ) on Binomial heaps. Then create another heap, exactly the same. And merge the two. You can either draw on paper (preferred), or use some visualisation applet on the web. In latter case - explain what happens at each step.

5. Simulate the same operations on Fibonacci heaps using some visualisation tool (search Google; - there are some linked from Wikipedia and also more). Can you estimate how much less or more work the Fibonacci heaps required in this case as compared to Binomial heaps?

6. Bonus 1p - for solving all of the 5 above tasks. + Bonus 2p Use the flow network from below. Calculate the maximum flow according to algorithm presented in the lectures (Ford-Fulkerson).

edit