hw1

50 %
50 %
Education

Published on March 21, 2008

Author: Manlio

Source: authorstream.com

Homework 1:  Homework 1 Problem 1: (5 points) Both Dijkstras algorihm and Bellmanford Algorithm generates shortest paths to all destinations. Modify the algorithm to compute shortest paths to a single specified destination and analyze its complexity. Problem 2: (5 points) Can you modify Dijkstras algorithm to generate shortest paths to all vertices from a given source vertex, if all these vertices are connected to the source vertex, and detect that the graph is not connected if the source is not connected to some vertices? Slide2:  Problem 3: (5 points) Generate a counter example where Dijkstras algorithm fails to generate shortest paths in graphs with negative edge weights, but no non-positive weight cycle. Problem 4: (5 points) Give an algorithm for computing the maximum weight spanning tree in a graph and analyze its complexity. Slide3:  Problem 5: (10 points) Consider two graphs G and G’ which are identical except the weights of the edges. Weight in edge e of graph G is w(e) >=0, and weight in edge e of Graph G’ is aw(e) + b, where a and b are constants. Are the minimum spanning trees of G and G’ identical? Are the shortest paths between any two vertices in the two graphs identical? Justify your answer. (If you answer positive, then prove your answer. If you answer negative, then give counter examples). If you answer negative for any of these, can you think of conditions on a and b, for which your answer would be positive? Suppose the weight of an edge e in graph G’ is 1/w(e). Is the minimum weight spanning tree in G the maximum weight spanning tree in G’ and vice-versa? Justify. Slide4:  Problem 6: (5 points) Consider the minimum steiner tree problem. Suppose someone tells you the intermediate vertices in a minimum steiner tree (intermediate vertices are the ones which are not the vertices in the multicast group). Can you present a polynomial complexity algorithm to compute the minimum steiner tree? Analyze its complexity. Problem 7: (5 points) Consider a vertex v. Does the mnimum spanning tree always consist of shortest paths from v to all other vertices? Slide5:  Problem 8: (10 points) Prove that the markov chain representing the wireless network taught in lectures 2 and 3 has one closed set, and possibly a few other open sets, under the routing and scheduling policy discussed in class. Also prove that the closed set has period 1, under certain assumptions on the arrival probabilities. You may assume that every packet has duration 1 slot. Problem 9: (10 points) Consider a network with a reward associated with every edge. The reward associated with every path is the minimum reward in any link in the path. Present an algorithm which computes the highest reward path between a source and a destination. Analyze its complexity. Slide6:  Problem 10: (15 points) Consider a unirate, multicast network with N sessions. Assume that the traffic for every session traverses a predetermined route. Construct a unicast network with N sessions with predetermined routes for each session such that a feasible rate vector in the unirate, multicast network is a feasible rate vector in the unicast network and vice versa. (The size of the unicast network will be larger than the size of the multicast network). Now consider a multirate, multicast network with M virtual sessions. Again assume that the traffic for every session traverses a predetermined route. Construct a unicast network with M sessions with predetermined routes for each session such that a feasible rate vector in the multirate, multicast network is a feasible rate vector in the unicast network and vice versa. (The size of the unicast network will be much larger than the size of the multicast network).

 User name: Comment:

January 18, 2019

January 18, 2019

January 18, 2019

January 18, 2019

January 18, 2019

January 18, 2019

Related pages

Schwäbische-Alb-Nordrand-Weg (HW 1) | Schwäbischer ...

Weitere Informationen zum Schwäbische-Alb-Nordrand-Weg (HW1): Hinweise zu den beiden Albrandwegen (HW1 und HW2) Wanderkartenübersicht (grafisch) über ...

Gesamtroute | Schwäbische Alb Tourismusverband

Der Albsteig (HW1/Schwäbische Alb Nordrandweg) schlängelt sich auf gut 350 km zwischen Donauwörth und Tuttlingen entlang des Albtraufs, der Steilflanke ...

Albsteig | Schwäbische Alb Tourismusverband

Immer am Albtrauf entlang führt der Albsteig (HW1) auf gut 350 Kilometern von Donauwörth bis Tuttlingen über Höhen von 400 bis über 1000 Metern. Der ...

Albsteig (HW1) - Qualitätswanderweg - Gesamtroute ...

Immer an der Kante lang schlängelt sich der Albsteig, auch bekannt als HW1 oder Schwäbische Alb Nordrandweg, zwischen Donauwörth und Tuttlingen ...

HW1: Von Gingen a. d. Fils nach Owen Teil2 • Fernwanderweg ...

HW1: Von Gingen a. d. Fils nach Owen Teil2 - Fernwanderweg - Schwäbische Alb

Wanderkartenübersicht HW1 | Schwäbischer Albverein – Wege

Grundsätzlich stehen zwei verschiedene Kartenwerke zur Verfügung, die Freizeitkarten 1:50.000 und die Wanderkarten 1:35.000. Übersicht der ...

SS-HW1 Technische Daten | Lautsprecher | Sony DE

Sony SS-HW1: Lernen Sie mehr über technische Daten & ob sich diese Lautsprecher auf Ihre Bedürfnisse ausrichten.

'Schwäbische Alb Nordrandweg HW1 (Übersicht/Gesamtstrecke ...

Wanderkarten: Schwäbische Alb Nordrandweg (3 Karten)1:50.000 L7330 Donauwörth L7328 Höchstädt an der Donau L7128 Nördlingen L7126 Aalen L7326 ...