22C:21: Computer Science II: Data Structures

What to submit for Project 1.

Note: Please do not submit code that does not compile.
  1. A generic class called myListGraph in a file called myListGraph.java. In addition to the methods in the version of myListGraph class posted on the course page, this class should contain new methods
    		double clusteringCoefficient(anyType v)
    		double clusteringCoefficient()
    		double averagePathLength()
    		GenericLink<anyType>[] breadthFirstSearch(anyType source)
    It is okay to add other methods that you consider useful. Ignore Items (2) and (6) in the Implementation section of Project 1 handout.
  2. A class called SmallWorldGraph in a file called SmallWorldGraph.java. The purpose of this class is to construct small world graphs. This can be done in one of two ways:
    1. The class may contain a method such as
      public static myListGraph createSmallWorldGraph(int n, int d, double p)
      to construct an appropriate small world graph. This is similar to the method createUDG in the posted version of the SmallWorldGraph class.
    2. Alternately, the smallWorldGraph class could be a subclass of the myListGraph<Integer> class and would contain a constructor
      public smallWorldGraph(int n, int d, double p)
      This is similar to the constructor
      	public unitDiskGraph(int n, int d)
      in the posted version of the unit Disk Graph class.

  3. A program called Experiments.java that contains code to perform the experiments described in the project handout. In other words, this program would generate small world graphs with different values of p, compute the clustering coefficient and average path lengths of these graphs, and output these quantities.

  4. Helper class such as: GenericLink.java, GenericLinkList.java, Point.java, and GenericQueue.java.

  5. A README file that (i) specifies how to compile and run your program, (ii) which subset of the tasks mentioned in the Project 1 handout are successfully completed by your program, and (iii) all known bugs or unusual behaviors in your program. The README file should be about half a page long.

  6. A 5-page report called smallWorld.pdf that reports on your experimental results. The report should have a title, introduction, and conclusions. It should contain plots of your data and a discussion on whether or not your experiments support or reject the hypothesis. If your experiments are not conclusive either way, your report should discuss other experiments that might be performed to test the hypothesis conclusively. Your report should also compare your experimental results with those reported in the Watts-Strogatz paper.