CSC2281 Quiz 4

Spring 2012
Herbert J. Bernstein ( )

CSC2281 Quiz 4
Spring 2012

 		 

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

This is the fourth daily quiz to be taken by Friday, 24 February 2012. It should take you between half an hour and 2 hours to answer the following questions. To do this quiz, you should use the java program provided on the assignments page. You wil have to change the program several times to do the different questions. You are permitted to get help in doing this from any source, but you are responsible for understanding everything you submit. You will be asked about it.

  <==== 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). All the questions will be based on the following graph:

  1. Respecting the indicated directions of flow, identify a minimal cut for the flow from A to N. You cut must be minimal both in terms of it not be possible to remove any edge from the cut and still disconnect the graph and also being of minimal capacity.

  2. Respecting the indicated directions of flow, and treating the capacities as if they were reciprocals of distance metrics, find the shortest distance from A to N. Thus a zero capacity is an infinite distance.

  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. Redo problem 2 treating the same graph as undirected.

  5. Describe in detail one practical algorithm for computing the maximal feasible flow from node A to node N, using the residual capacity on an augmented graph.

  6. Give the status of your project. 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