CSC2281 Quiz 3

Spring 2012
Herbert J. Bernstein ( )

CSC2281 Quiz 3
Spring 2012

 		 

This web page is http://www.bernstein-plus-sons.com/.dowling/CSC2281S12/CSC2281_Quiz_3.html
Copyright © 2011, 2012 Herbert J. Bernstein and other parties. All rights reserved.

This is the third daily quiz to be taken by Friday, 17 February 2012. It should take you between half an hour and 2 hours to answer the following questions. You should be sure to read Chapter 2 (pp 37 -- 58) of H. J. Bernstein, M. Goldstein, "Network Design and Implementation Lecture Notes Spring 1984" as well as chapters 1, 2 and 9 of Hwei Hsu ,"Schaum's Outline of Probability, Random Variables, and Random Processes".

  <==== Do this AFTER you've answered all the questions

You probably DON'T want to do this ===>  

Please fill in the following information:

Name:


Email:

Skype ID:

Please answer the following questions on this form (or on a paper copy of this form). The first five questions will be based on the following graph:

With the following capacities: AB = 5, AC = 8, BF=12, EJ=18, LN=7, MN=4, IN=6, and all others =3.

  1. Respecting the indicated directions of flow, identify a minimal cut for the flow from A to N.

  2. Respecting the indicated directions of flow, and treating the capacities as if they were distance metrics, find the shortest distance from A to N.

  3. Redo problem 1 for an undirected graph, i.e. treat every edge as if it has an edge of the same capacity in the other direction.

  4. Using the undirected graph in problem 3, and Dijkstra's algorithm, compute the shortest paths from node A to every other node.

  5. Describe in detail one practical algorithm for computing the maximal feasible flow from node A to node N.

  6. Explain the conflict between response delays and throughput.

  7. What is a reasonable, simple assumption about the relationship between service rates and line capacity?

  8. What are Lagrange multipliers?

  9. Give Kleinrock's formula for optimal line capacities in terms of delay.

  10. Discuss qualitatively when indirect routing is better than direct routing.

  11. Summarize how you can use queuing theory and graph theory to design a network.

  12. Describe your proposed project for this course in detail explaining how you will make use of the tools of queuing theory and graph theory in your project. Once again, if you will be part of a team, list the members of your team and give their email addresses. Each team member should, hopefully, be giving the same list for the team they are on.

  <==== Do this AFTER you've answered all the questions

You probably DON'T want to do this ===>  

Revised 5 February 2012