CSE 373: Data Structures and Algorithms, Winter 2013

Homework 8 (Six Degrees of Kevin Bacon) FAQ

Q: What are some good resources or examples I can look at to get started on this program?

A: Look at the lecture slides to see pseudo-code for each graph searching algorithm. If you want to read more about graph algorithms, see Chapter 9 of the Weiss textbook.

Q: How do I attach the Graph.jar and Guava JAR files to my project?

A: in Eclipse:

1. Download the Graph.jar archive.
2. Download Guava JAR archive from http://code.google.com/p/guava-libraries/ (if you don't already have it).
3. Attach each JAR to your Eclipse project. Right-click the project in the left side Package Explorer, and choose Build Path → Add External Archives ...
4. In the box that pops up, browse to the Guava or Graph JAR and select it.

in jGRASP:

1. Download the Graph.jar archive.
2. Download Guava JAR archive from http://code.google.com/p/guava-libraries/ (if you don't already have it).
3. Click Settings → PATH/CLASSPATH → Workspace.
4. A dialog box pops up. Click the CLASSPATHS tab.
5. Another box pops up. Click New. Click Browse.
6. Now a file browser pops up. Go find the location of your .jar file and select it.
7. Click OK until you're back at your code.

Q: In Part A, why does the graph always return false or null when I try to search for paths?

A: If you have a SearchableGraph.java file in your project, Eclipse will use your SearchableGraph class instead of ours. So either remove that file from your project or don't add it yet, until you are done with Part A.

Q: In Part B, why do I get a StackOverflowError when trying to make a depth-first search?

A: The recursion will only terminate if you are correctly "marking" vertices as "visited" each time. Make sure you set them to be visited and only make further recursive calls on a vertex if it is not visited. Also make sure that you are not clearing the vertex "visited" info on every recursive call, because doing so would wipe out your memory of which vertices have been visited.

Q: In Part B, why am I sometimes getting paths with a negative weight?

A: Some of the path search algorithms say that you should set a vertex's cost to "infinity". If you use the value Vertex.MAX_COST to represent infinity, which we recommend, it has the value of Integer.MAX_VALUE, which is the largest value that can be stored as an int (it's equal to 2³¹ - 1, if you are curious). But if you ever add to this value, you will get an integer overflow, which causes the resulting number to become negative. So be careful that you are not computing Vertex.MAX_COST + something in your code.

Q: In Part B, why am I sometimes getting paths with a negative weight?

A: Some of the path search algorithms say that you should set a vertex's cost to "infinity". If you use the value Vertex.MAX_COST to represent infinity, which we recommend, it has the value of Integer.MAX_VALUE, which is the largest value that can be stored as an int (it's equal to 2³¹ - 1, if you are curious). But if you ever add to this value, you will get an integer overflow, which causes the resulting number to become negative. So be careful that you are not computing Vertex.MAX_COST + something in your code.

Q: In Part A, I run out of memory when I am trying to run the large test cases on imdb.txt. How can I fix this?

A: You don't NEED to run these big tests to complete the assignment; they are just for fun. If they don't work and complain about being out of memory / heap space, you can increase the memory limits. In Eclipse:

1. Click Window → Preferences. A preferences dialog box pops up.
2. Click Java → Installed JREs. click the currently checked JRE from the list at right. Click Edit... An "Edit JRE" dialog box pops up.
3. Under Default VM Arguments:, you can indicate how much memory you want in an odd format: -XmxNUMBER-OF-MEGABYTESm . So, for example, to give it 1000 megabytes of memory, write:   -Xmx1000m .
   

in jGRASP:

1. Click Settings → Compiler Settings → Workspace.
2. A dialog box pops up. Make sure the "Compiler" tab is selected and the "Flags / Args" tab selected under that.
3. In the "FLAGS2 or ARGS2" column, find the "Run" row and click the weird black square box next to it to un-check that box. The text box should light up white so that you can type into it. In the box, you can indicate how much memory you want in an odd format: -XmxNUMBER-OF-MEGABYTESm . So, for example, to give it 1000 megabytes of memory, write   -Xmx1000m .