Description
A. Graph algorithms. You may find the following Wikipedia article useful:
https://en.wikipedia.org/wiki/Distance_(graph_theory)
1. [Writing] What is the eccentricity of a vertex in a graph? Illustrate with an example.
2. [Writing] What is the radius of a graph? Illustrate with an example.
3. [Writing] What is the diameter of a graph? Illustrate with an example.
(10 marks)
4. [Algorithm Design] Provide detailed algorithmic solution to compute the three
properties. You may use functions such as BFS, DFS, and Dijkstra.
5. [Complexity Analysis] What are the computational complexities of the three solutions?
(30 marks)
B. You are given a data file containing pairs of the names of UOIT faculty instructors. It can be
obtained at:
https://db.science.uoit.ca/share/instructor-pair.txt
Each pair has shared at least one course in common since 2014.
From the file, construct a bidirectional graph. The vertices are the instructors, and an edge
exists between x and y if they have shared a course. Namely, either (x, y) appears in the file or
(y, x) appears in the file.
Create the adjacency matrix of the graph G. You must short the adjacency list alphabetically.
1. [Program] Use BFS to list all the instructors which are connected (directly or indirectly)
to “Ken Pu”.
2. [Program] Use DFS to list all the instructors which are connected to “Ken Pu”.
3. [Program & Writing] How many connected components are there? With the help of
Google, describe what each connected component represents.
4. [Program & Writing] For each connected component, measure the number of vertices
and the radius of each component. Tabulate your results. Can you gain some insight
into the components?
(60 marks)
Submission:
You must submit a directory with the following structure
.
├── report.pdf
└── src
├── B1.java
├── B2.java
├── B3.java
├── B4.java
└── Makefile
If you use Python, all *.java files should be *.py files respectively. You are free to include other
files for the sake of code organization.
You mustinclude a Makefile with at least the following targets defined:
make B1
make B2
make B3
make B4
make clean