CSC2281 Quiz 2

Spring 2012
Herbert J. Bernstein ( )

CSC2281 Quiz 2
Spring 2012

 		 

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

This is the second daily quiz to be taken by Friday, 10 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 1 (pp 1 -- 35) of H. J. Bernstein, M. Goldstein, "Network Design and Implementation Lecture Notes Spring 1984" all the way through the section on graph theory and then read the Cook text chapters 1 through 3. Your objective is to be able to start work with the Ford-Fulkerson Max-Flow-Min-Cut algorithm, so you can find the maximal flows on networks. By the end of the semester you will need to be able to do real calculations optimizing real networks.

  <==== 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).

  1. Define a directed graph.

  2. Define an adjacency matrix, giving an example.

  3. What limits the maximal flow through a network?

  4. In words, not code, give an algorithm to determine the shortest path between two nodes in a directed graph.

  5. Suppose you have a directed graph with 9 nodes, A, B, C, D, E, F, G, H, I, and edges (A,B), (B,C), (C,D), (D,E), (E,F), (F,G), (G,H), (H,I), (I,A), (C,F), (G,B), (D,H), (H,B). Carefully write the adjacency matrix for this directed graph.

  6. Using the directed graph in problem 5 (mistakenly numbered 1 in the prior version of this quiz), and Dijkstra's algorithm, compute the shortest paths from node C to nodes A, B, D, E, F, G, H and I. Show your work.

  7. Redo problem 5 (mistakenly numbered 1 in the prior version of this quiz) for an undirected graph.

  8. Using the undirected graph in problem 7 (mistakenly numbered 3 in the prior version of this quiz), and Dijkstra's algorithm, compute the shortest paths from node C to nodes A, B, D, E, F, G, H and I. Show your work.

  9. Consider a finite (undirected) graph of 201 vertices, numbered 1 through 201. Suppose each even numbered vertex has an edge to the two odd numbered vertices above and below it in sequence. Suppose each odd numbered vertex in the range 1 through 199 also has an edge to vertex 201. Is the number of edges incident on vertex 201 odd or even? Why?

  10. Take the graph from problem 9 (mistakenly numbered 1 in the prior version of this quiz) and assign a cost to each edge equal to the square root of the magnitude of the difference in ordinals of the vertices incident on the edge. Find a minimal cost path from vertex 3 to vertex 198, from vertex 8 to vertex 3, from vertex 8 to vertex 198.

  11. Take the graph from problem 9 (mistakenly numbered 1 in the prior version of this quiz) and make it into a directed graph by directing all edges from lower numbered vertices to higher numbered vertices, except at vertex 201. At vertex 201 direct the edges out if they go to odd numbered vertices, and in from even numbered vertices. Assign a capacity to each edge equal to the magnitude of the difference in ordinals of the vertices incident on the edge. Find the maximal feasible flow from vertex 3 to vertex 198, from vertex 8 to vertex 3, from vertex 8 to vertex 198.

  12. Briefly describe your proposed project for this course. 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 25 January 2012