50 %
50 %
Information about hw1soln

Published on March 21, 2008

Author: Dario

Source: authorstream.com

Solution to HW1:  Solution to HW1 Problem 1:  Problem 1 Need to find shortest path from a single source s to a single destination d. Have a condition in the Dijkstra algo loop which terminates the process whenever v is inducted into the set S. Problem 2:  Problem 2 Whenever some node v is inducted into S such that d(v) = , then we know the graph is disconnected. When a vertex v is inducted into S, d(v) is the shortest distance from s to v. If this shortest distance is infinity, then s is disconnected to v. Problem 3:  Problem 3 All answers were correct! Problem 4:  Problem 4 Given a graph, construct a new graph with same nodes and edges, weight of an edge = negative of weight of the corresponding edge in the given graph. Minimum spanning tree in this new graph is maximum weight spanning tree in the old one. Problem 5:  Problem 5 MST s are identical if a0, otherwise they may be different (two MSTs have same number of edges). Shortest paths are identical if a0 and b=0. Yes, with reciprocal edge weights, minimum weight spanning tree becomes maximum weight spanning tree. Slide7:  Now the light weight edge crossing a cut in one is the heavy weight edge crossing the cut. By choosing the heavy weight one we get maximum weight spanning tree. By choosing the light weight one we get minimum weight spanning tree. The same sequence of choices in Kruskals leads to minimum spanning tree in one and max. spanning tree in another. So, minimum spanning tree in one is identical to the maximum spanning tree in another. Problem 6:  Problem 6 We know all the vertices in the Steiner tree given the intermediate ones. Need to find a minimum spanning tree in the induces subgraph. Problem 7:  Problem 7 No. All counter examples were valid! Problem 8:  Problem 8 The system can be represented with the queue lengths of different sessions in different buffers. The state process is a markov chain. Let the current state of the markov chain be (…..Bi1(t), Bi2(t),….. ) There is a positive probability of 0 arrival in this state If there is no arrival, then it moves to a state where total number of packets in the system is lesser, or equal but packets have moved closer to the destination. Slide11:  Given a particular state, there is a finite time such that if there is no arrival in any slot in that time interval, then the system moves to all zero state. Given any finite number of slots, there is a positive probability that the number of arrivals is 0 in each of these slots. There is a positive probability path from each state to the all zero state. Every state communicates to the all zero state. Slide12:  All zero state communicates to some states. All states which have positive probability path from the zero state, communicate with each other, and does not communicate to any state which does not have a positive probability path from the all zero state. All states which have positive probability path from the zero state constitute a closed set (along with the all zero state). All other states communicate to the zero state, and the zero state does not communicate to them. So all other states are open. Problem 9:  Problem 9 Sort all the reward values. (1)Remove all edges with reward value less than R R = highest reward value. Find whether source is connected to the destination. If so, stop. If not, reduce R to the next highest reward value and go to step (1) The final value of R is the highest reward and the final path is the highest reward path. Slide14:  Complexity is O(E2) Can do a binary search on the reward values, complexity will be O(ElogE) Problem 10:  Problem 10 Unirate Multicast The feasible set looks like ri + rj + ….. rp  Cl (constraint for link l) ………………. ……………………….. For every link constraint, create a link in the new unicast network, with all sessions appearing in the constraint traversing the link. The capacity of this link is the same as the capacity of the link in the constraint. Slide16:  Consider any session i. Join all the links traversed by session i by links of very high capacity. Every session is unicast in this network. The number of sessions is the same in both networks. The number of links are N(L + 1) in the new network. The feasibility constraints are identical in both links. Hence, the feasible sets are identical. Multirate Multicast Network:  Multirate Multicast Network The constraints are max(ri , rj , ….. rp) + max(…..) + ….  Cl Replace each constraint by linear constraints. Consider an example: max(r1 , r2 ) + r3  Cl The equivalent linear constraints are: r1 + r3  Cl , r2 + r3  Cl Slide18:  Consider an example: max(r1 , r2 ) + max(r3 , r4 )  Cl The equivalent constraints are: r1 + r3  Cl , r2 + r3  Cl r1 + r4  Cl , r2 + r4  Cl If there are L links in the network, there can be at most mN L linear constraints, where m is the maximum number of receivers in the network, and N is the number of sessions. Slide19:  These constraints are of the form ri + rj + ….. rp  Cl And involve r1 , r2 , ….. rM Proceeding in the same manner as for unirate multicast, we can now get a unicast network of M sessions, mN L(M + 1) links. A multirate, multicast can be reduced to unicast network, but the unicast network has exponentially larger size!

Add a comment

Related presentations

Related pages

HW1soln - Course Hero

HW1soln Home. Washington State. CHEM. CHEM 532. HW1soln. Download Document. Showing pages : 1 - 7 of 7. This preview has blurred sections. Sign up to view ...
Read more

HW1soln - coursehero.com

View Notes - HW1soln from CHEM 532 at Washington State.
Read more

hw1soln - Tufts University

ES-7A Thermodynamics HW 1: 2-30, 32, 52, 75, 121, 125; 3 -18, 24, 29, 88 Spring 2003 Page 3 of 6 2-75 Ideal Gases Given: 1 m³ tank containing air at 25 ...
Read more

HW1soln - Ace Recommendation Platform - 1

HW1soln. We found 20 results related to this asset. Document Information; Type: Problems & Answers; Total # of pages: 8. Avg Rating: Price: ...
Read more

hw1soln - Ace Recommendation Platform - 1

Assignment 1Due Friday 1/27/12 (by noon to Gayle Travis in ZEC 241)Reading: Required: Undergraduate Probability I Chapters 1-4 Required: First Course in ...
Read more

hw1soln.pdf - Mechanical Engineering 365 with Meckl at ...

Study online flashcards and notes for hw1soln.pdf including ME 365 HOMEWORK SOLUTIONS FALL ...
Read more


CS 3114 Data Structures & Algorithms Homework 1: Trees 2 3. [25 points] Suppose you have a collection of N different points in the xy-plane, where N is large.
Read more

hw1soln.html - University of North Carolina at Chapel Hill

1. Write down the sample space an experiment consisting of three tosses of a coin. Is it finite or infinite? The sample space is finite. 2. A letter is ...
Read more

10. (a) (b) = s,X3 = t where s and t are arbitrary values ...

10. (a) (b) = s,X3 = t where s and t are arbitrary values — s, y = t, z = u where r, s, t, and u are arbitrary values 4. (b) We can solve this system by ...
Read more