Description
1. [90%] Randomly create an undirected complete graph as follows:
• Create n vertices where n is randomly selected between 5 and 10. Display the
selected n value.
• Create an n x n adjacency matrix A. Randomly assign a weight to each edge (i,j)
where 1 ≤ i, j ≤ n. Specifically, make A[i,j] = 0 if i = j. If i ≠ j, assign an integer randomly
selected between 1 and 10 to A[i,j]. Ensure that A[i,j] = A[j,i] since you need to
create an undirected graph. Display the generated adjacency matrix.
For the created undirected complete graph, do the following:
1) [45%] Implement Prim’s minimum spanning tree algorithm by programing priority
queue either as array or heap data structure (Chapter 9). Print all the edges in the
generated minimum spanning tree.
2) [45%] Implement Kruskal’s minimum spanning tree algorithm using the find3() and
union3() functions in the lecture notes (Chapter 10). Print all the edges in the
generated minimum spanning tree.
• Note 1: Please let a user select one of the above two algorithms. Return an error
message, if the selected algorithm is other than the above two algorithms.
• Note 2: You are supposed to implement the algorithms correctly for random
undirected graphs as described above. If your program produces correct results for
some graphs but doesn’t for other graphs, you will get zero.
• Note 3: For grading purposes, don’t pass any parameter to your main() function. You
will lose 10% if you violate this requirement. If everybody follows this rule, grading
may finish earlier.
2. [10%] 10% of the grade will be based on good coding style and meaningful comments.
All programming must be done using C or C++ in Linux where your code will be tested.
Create a tar file that includes (1) source code files, (2) a Makefile to produce an executable,
and (3) a readme file that clearly describes how to run your code. Submit only the tar file
through the Blackboard. The name of the tar file should be yourlastname_yourfirstname
_proj4.tar (Do not use special characters like #, @, or &, because they have caused
Blackboard problems in the past.) Suppose that your assignment files are under the
directory of /your_userid/yourlastname_yourfirstname_proj4/ and you are under that
directory right now. To create a tar file under /your_userid directory, do the following in
Linux command line:
>cd ..
>tar cvf yourlastname_yourfirstname_proj4.tar yourlastname_yourfirstname_proj4
To view the content of the created tar file, do the following in Linux command line:
>tar tvf yourlastname_yourfirstname_proj4.tar
Finally, read the following policies carefully:
• All work must represent each individual student’s own effort. If you show your code or any
other part of your work to somebody else or copy or adapt somebody else’s work found
online or offline, you will get zero and be penalized per the Watson School Academic
Honesty Code (https://www.binghamton.edu/watson/about/honesty-policy.pdf).
• To detect software plagiarism, everybody’s code will be cross-checked using an automated
tool.
• Your code will be compiled and executed. If your code does not compile or produce any
runtime errors such as segmentation faults or bus errors, you will get zero.
• The instructor and TA will not read or debug your code. The instructor and TA will not
take a look at an emailed code. If you need general directions, show your code to a TA
during her office hours. The TA will not do programming or debugging for you though.
The TA will only help you understand algorithms to be implemented and answer basic
questions related to implementation.
