Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

CS 165 - Project in Algorithms and Data Structures

CS 165 - Project 3 - Algorithmic Experiments of Real-World Phenomena
100 points

Please submit your project electronically, with the source code as a single zip file and your report as a single pdf file.

Project 3 involves testing various graph algorithms experimentally to determine properties of models of real-world networks. The specific graph algorithms you should implement are the following three algorithms (please see the course notes for details on these algorithms):

1. Diameter algorithm, that is, as best is reasonably possible, determine the length of a longest path in the graph.
2. Clustering-coefficient algorithm, that is, determine the ratio of three times the number of triangles over the number of paths of length 2.
3. Degree-distribution algorithm, that is, determine for each possible degree, the number of vertices in the graph with that degree.

You need to test each algorithm on graphs of the following type (depending on your student ID):

• If your student ID is an odd number, you should test the above algorithms on Erdos-Renyi random graphs, G(n,p), with p = 2(ln n)/n, where "ln n" denotes the natural logarithm of n.
• If your student ID is an even number, you should test the above algorithms on Barabasi-Albert random graphs, generated with the parameter d = 5 as the number of neighbors each new vertex chooses.

You should determine the diameter and clustering coefficients of multiple random graphs of length n, and have n grow, and then plot the average diamters and clustering coefficients, respectively, as a function of n, on a lin-log scale. You should then make a determination as to whether these values grow, decrease, or remain constant as a function of n. Also, if they grow, determine if they grow proporitonal to the function, log n, or according to a function that grows faster or slower than the function, log n.

For each number of vertices, n=1,000, n=10,000, and n=100,000, plot the degree distribution of an instance of your chosen type of random graph having that number of vertices. You should plot the degree-distribution results on a regular (lin-lin) scale and a log-log scale, and then make a determination whether that degree distribution has a power law. If you decide that the degree distribution has a power law, find the slope of a line fitting the data in the log-log scale and report on the exponent of that power law.

Please use the file, project3.h file to define your API. (Updated May 30, 2019.)

Here is a test file, tests.h, which you should use to test your code. It is similar to the test file that will be used by the Grader.

Write a report that shows your plots, includes your conclusions, explains how you implemented your algorithms (including pseudo-code for your versions), and any other observations that you would like to make.

There will be 10 points of extra credit available to students who implement and test both types of graph models, Erdos-Renyi and Barabasi-Albert, including plots and analysis in their report for both types.