Describe the steps involved in network simplex method, Computer Networking

Assignment Help:

QUESTION 1:

(a) Define what you understand by the following terms in Network Flows:

i) UnDirected Path
ii) Directed Path
iii) Directed Cycle.
iv) Tree

In each of the above, show the differences in terms of nodes and directions.

(b) In Radix Heap Algorithm, the technique of buckets is employed. However this idea is an extension of Dial's Algorithm. Analyse the complexity of Radix Heap Algorithm referring to:

1. Movement of nodes between buckets
2. Node Selection principle

QUESTION 2:

(a) Below is the algorithm of a flow decomposition algorithm.

begin
Initialize
while y ≠ Φ do
begin
              Select(s, y)
              Search(s, y)
              if a cycle C is found then do
              begin
                            let D = Capacity(C, y)
                            Add Flow(D, C) to cycle flows
                            Subtract Flow(D, C) from y.
              end
              if a path P is found then do
              begin
                           let D = Capacity(P, y)
                           Add Flow(D, P) to path flows
                           Subtract Flow(D, P) from y.
               end
end

Describe the complexity of the following:

i) Selecting the initial node,
ii) Finding a cycle or a path,
iii) Update step.

(b) Explain how Lower Bounds on Arc Flows are eliminated. Show your workings by a mathematical representation or otherwise.

(c) Refer to the diagram below, show how we could always provide a flow of at most 10 on Node 4.

                          1881_11.png

QUESTION 3:

(a) Briefly describe the steps involved in Network Simplex Method.

(b) Referring to Dial's Algorithm and assuming C, to be the Largest arc length, complete the table below.

Variables                                   Cost Value
Number of buckets needed
Time to create buckets.
Time to update d() and
buckets.
Time to find min.
Total running time.

(c) Using Kruskal's algorithm, find the minimum spanning tree of the graph as show in Figure 3.1.

                              1776_11.png

                                                       Figure 3.1

(d) Give mathematical models for the 0-1 knapsack problem and the bounded knapsack problem in Dynamic Programming.


QUESTION 4:

(a) Write down a Generic Label Correcting Algorithm.

(b) Explain how you could detect Negative Cost Cycles in a given set of flows.

(c) Prove that a Negative Cycle Algorithm terminates with an optimal flow.


Related Discussions:- Describe the steps involved in network simplex method

Systolic array, Systolic Array This interconnection network is a kind o...

Systolic Array This interconnection network is a kind of pipelined array architecture and it is designed for multidimensional flow of data. It is used for executing fixed algor

What is a tag, In HTML, a tag shows the browser what to do. When you write ...

In HTML, a tag shows the browser what to do. When you write an HTML page, you enter tags for lot of  reasons -- to change the appearance of text, to show a graphic, or to make a co

Calculate the efficiency of stop-and-wait ARQ, Suppose that frames are 1250...

Suppose that frames are 1250 bytes long including 25 bytes of overhead. Also assume that ACK frames are 25 bytes long. Calculate the efficiency of stop-and-wait ARQ (a) Transmits a

Computer networks - fundamentals of networks , Computer Networks A com...

Computer Networks A computer  networks  can be defined as set of computer that  interact  among  the individual  computers sharing  resources or information. Reference models

Processor arrangements-array, Processor Arrangements It is a very frequ...

Processor Arrangements It is a very frequent event in data parallel programming to group a number of processors to perform definite tasks. To reach this goal, HPF gives a direc

Tcp connection management , TCP Connection Management TCP connection ...

TCP Connection Management TCP connection management encompasses the procedures for establishing and  terminating connection (FTCP is  connection oriented protocols). In TCP c

Describe about packet switching, Q. Describe about Packet Switching? P...

Q. Describe about Packet Switching? Packet Switching - Data are transmitted in separate units - Called Packet - Packets are variable length blocks - The max leng

What is bandwidth, Question 1 What is bandwidth?                         >...

Question 1 What is bandwidth?                         >>What is the bandwidth of                            a) Telephone signal                            b) Commercial radio broa

How is an intranet different from an internet, QUESTION a) How is an In...

QUESTION a) How is an Intranet different from an Internet? b) State the main differences between a router and a switch c) Explain the function of a modem d) Calculate

Session layer standards, Session layer protocols consists of NFS, SQL, RPC,...

Session layer protocols consists of NFS, SQL, RPC, Appletalk Session Protocol (ASP), XWindows, and NetBEUI.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd