I need real computer programming and Math expert !!

Winter 2014 Math 330 Homework IV

For Problems 1 to 4, determine the following properties of the network.

(a) Switch Type

(b) Number of Switches

(c) Diameter

(d) Maximum Congestion

IV.1 The network below with N = 3 inputs and N = 3 outputs.

0

��

1

��

2

�� ◦ )) ◦ ))ii

��

◦ ))ii ◦ ))ii

��

◦ ))ii ◦ii

��

0 1 2

IV.2 Extend the network in Problem 1 to an arbitrary N inputs and N outputs. If it makes it easier to assume that N is odd, even, or a power of 2, you may do that.

IV.3 The network below with N = 5 inputs and N = 5 outputs.

0

��

1

��

2

��

3

��

4

�� ◦ ))

��

◦ ))ii

��

◦ ))ii

��

◦ ))ii

����

◦ii

��

0 1 2 3 4

IV.4 Extend the network in Problem 3 to an arbitrary N inputs and N outputs. If it makes it easier to assume that N is odd, even, or a power of 2, you may do that.

—1—

Winter 2014 Math 330 Homework IV

IV.5 Provide a Butterfly network routing for π given below. What is the congestion of the routing?

π(0) = 3 π(4) = 2

π(1) = 1 π(5) = 0

π(2) = 6 π(6) = 7

π(3) = 5 π(7) = 4

IV.6 Provide a Beneš network routing for π given in Problem 5 that has a congestion of 1.

IV.7 Given the network below, determine the maximum flow from S to T. Find the minimum cut set that shows that you have found the maximum flow.

• 3 1

•

1

5

s

5

4

3

• 2

3

t

• 1

3 • 8

IV.8 Use the maximum flow algorithm to determine a maximal matching of the following candidates and employers.

Candidate Acceptable Matches Alice Apple, Google Bob Google Carol Apple, HP, IBM Dave Google, Sun Eliza Google, Sun

—2—