CS 3343, Recitation 11, Hints

CS 3343/3341
Analysis of Algorithms

Recitation 11
Hints

Typographical Errors in Problem 1 ( Rec 11, in-class). (These errors have been corrected.)

In the description, edgeDistance should be edgeLength (twice).
In the code on the left, edgeDist should be edgeLen, and on the right edgeDist should be edgelen.

Chasing down the Adjacency List. Problems 1a, 1b, and 1d each require code that will chase down the adjacency list for a given vertex, doing something with each item (= edge) on the list. Most of you have probably successfully done this already, but if you are still having trouble, here is code to do it:

In Java Language	In C Language
Edge e = graph[i].firstEdge; while (e != null) { // do something with edge e // ... // move to next edge (if present) e = e.nextEdge; }	*struct edge e = graph[i] -> firstedge; while (e != NULL) { // do something with edge e // ... // move to next edge (if present) e = e -> nextedge; }**

In Java Language

In C Language

Edge e = graph[i].firstEdge;
while (e != null) {
   // do something with edge e
   //   ...
   // move to next edge (if present)
   e = e.nextEdge;
}

struct edge* e = graph[i] -> firstedge;
while (e != NULL) {
   // do something with edge e
   //   ...
   // move to next edge (if present)
   e = e -> nextedge;
}

Input file for the "48 Capitals" example, used in Problem 1.

The input file for the Java version is given in the same table that contains the listing, on the page Graph Rep (Java). (Just copy and paste.)
For the C version of the program, the file has the first line missing, and the C code has the line #define GRAPHSIZE 48, but otherwise the file is the same.

"edgeLength" functon: This returns a value different from -1 only if the adjacency list for vertex (node) v1 has v2 as one of the entries.

Input file small.txt used in Problem 1. This is the file for the Java version. If you use my C code, then you need a file with the first line deleted and with the line #define GRAPHSIZE 11 in the C code.

Problem 2 of Recitation 1:

Initially you should implement this as shown in the pseudocode inside the white box under Problem2, the code that ends with hamPaths(10, 0, 0); which should be the initial call. Later you could try to use the initial call of hamPaths(8, 133, 2); if you wanted to (it is not required).
The code for the hamPaths function is remarkably simple and is almost completely described by the pseudocode. Some people found the statement
"For each vertex v in u's adjacency list do the following:"
confusing. This is not implemented with a for loop. It's just uses the same code to chase down the adjacency list that is given above.

Revision date: 2012-11-09. (Please use ISO 8601, the International Standard Date and Time Notation.)