CSC2281 Quiz 3

Spring 2013
Herbert J. Bernstein ( )

CSC2281 Quiz 3
Spring 2013

 		 

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

This is quiz 3 to be taken by Friday, 22 February 2013. 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 ,"Schaums 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. Remeber, if you will be a member of a team, you still have to have some significant component of the portfolio project that is your own personal origial creation. Be sure to identify that component.

  13. Give the URL for your blog for this course, identifing the specify blog entries that give your notes on each of the reading assigmments in the first three assignments. If you havent done those readings

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

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

Revised 27 January 2013