Introduction to the Design and Analysis of Algorithms
Textbook.
 CS 3343
 Analysis of Algorithms
 Fall 2012
 Recitation 13 
 DFS, Etc. 
    Week 13: Nov 20
 Due (on time): 2012-12-03  23:59:59
 Due (late):        2012-12-05  23:59:59

Recitation 13 should be submitted following directions at: submissions with deadlines
  • 2012-12-03  23:59:59 (that's Mon, 03 Dec 2012, 11:59:59 pm) for full credit.
  • 2012-12-05  23:59:59 (that's Wed, 05 Dec 2012, 11:59:59 pm) for 75% credit.

In-class Problems: The first problems will be made accessible during the Recitation hour: Rec 13, In-Class Problems (password protected, use "CS3343" without quotes for "User Name" and password from class just before the recitation).

  1. Depth-first Search. (See DFS) For this search, each vertex should have pi, color, d, and f fields as specified in your text. Notice that the d is used differently here, for "time discovered", while f stands for "time finished". (A global variable time provides a simulation of time passing during the algorithm.) You must use your text's DFS algorithm here. In particular, it must use recursion rather than a stack. You should run your DFS with the two standard graphs we've used. In each case you can start from whatever vertex you like, but it should be clear which one your start vertex is.

    1. The simple graph small.txt (which comes with an initial line "11" for the vertex count).
    2. The 48-capitals graph.

    Your run for each graph above must include:

    1. The depth-first search. This part requires no output, although you can accomplish part b either during the seach or as a separate step.
    2. A printout of the list of vertices along with their vertex data, that is, values of the d, f, and pi fields for each vertex, showing the course of the search and defining the depth-first spanning tree. Everything about the search from your chosen start vertex is implicit in this data.

  2. Depth-first Search and topological sort. In this part you must work with two examples from your text.

    1. First is the dag in Figure 22.7 on page 613. For use in our program, I've numbered the 9 vertices as: undershorts:0, socks:1, watch:2, pants:3, shoes:4, belt:5, shirt:6, tie:7, jacket:8. ["Undershorts"! What the hell? I looked this up in my paper dictionary, since it's obviously some archaic term. It said "See short 4b". OK, under that reference, it said: "pl: short drawers". What? This sounds actively scary. What is this guy wearing?]

      Notice that this is a directed graph, so we don't enter edges in both directions as we did before. It is also acyclic, meaning that there are no non-trivial loops. This is what your text calls a "dag", a "directed acyclic graph". The DFS has to start over again at several vertices, and the spanning tree is a spanning forest consisting of several trees. Here is a file with the edges: clothing.txt, with an initial record holding "9", the number of vertices.

      In order to carry out the topological sort, you add a single print statement after the part of the DFS that gives each f field its value, printing the vertex that gets assigned this value. This will print the vertices in reverse order from the order of topological sort. (See your text, page 613. You don't need to bother putting them into a linked list as your text suggests.) Notice that in general there will be many different correct topological sorts, so you should not expect to get the order shown in the image above. (In the image above, the finish time for "jacket" is 4 and it comes first. Next is the finish time for "tie" which is 5, and so forth, giving the topological sort backwards.)

    2. The second dag for a DFS and topological sort is from Figure 22.8 on page 615. The figure shows vertices labeled with letters from m to z, but in the data below, these are integers from 0 to 13.

      Here is a files with the edges: dag.txt with an initial record holding "14", the number of vertices. In this case the spanning tree is again a spanning forest, with three separate trees. Here again you should give the vertices in reverse order of a topological sort.

  1. Dijkstra's Algorithm. I decided not to require that you program this algorithm, but instead I want you to carry it out by hand. You should practice this, rather than program it because I will ask a similar question on the final. Here is a graph to which you should apply Dijkstra's algorithm. This includes deciding on the predecessor of each node (=vertex) as well as the distance from the source (the pi and d fields). In this example the nodes are named (a, b, ...) rather than numbered. The source vertex is a.

    For full credit you must show the relaxation steps and show how the values for distance and predecessor change to the final values. [I will give an answer to this before the final. For practice with Dijkstra's algorithm, here are 3 other graphs to process: practice graphs.]

Revision date: 2012-11-26. (Please use ISO 8601, the International Standard.)