PUSAT PENGAJIAN SAINS KOMPUTER
(School of Computer Sciences)
CPT212- Design and Analysis of Algorithms
Assignment II: Graph Algorithms
Release Date: 17th May 2021 (Monday)
Due Date: 20th June 2021 (Sunday) by 11:59pm sharp
Objectives
The purpose of this assignment is to test your understanding of graph representation and
algorithms. You will be required to code the actual algorithms to solve problems that have
been discussed in class.
Prerequisites
- Each group must consist of 3 individuals.
- Each group will have ONE wiki to document the functionality of their program.
- Each group must produce a ONE cohesive program (one source file or project file).
- You can choose to code in Python or C/C++ but choose only ONE.
- Please specify instructions on how to run your codes.
- You can use algorithms/codes from online sources to solve the given problems but
must be cited. - Although this is a group project, a large percentage of the grade will be individual
work (70% individual, 30% group).
Default Graph - Go to https://randomcity.net/ and pick 5 random cities and their corresponding
countries. - Go to https://www.distancefromto.net/ and find out the distance (in kilometers)
between each of these cities (you can round up/round down to get whole numbers). - Between each city, add only one directed, weighted edge.
- Example graph (you cannot use the exact same one):
Instructions - Choose ONE data structure to represent the graph (E.g., adjacency list, adjacency
matrix or incidence matrix). - There must be a list of common graph functions (E.g., add new edge, remove edge
etc.). These functions must be used to modify the graph. - The same data structure and functions must be used by every group member.
- Each time the program starts up, the default graph must be already initialized and
can be modified by any of the functions. Do NOT prompt the user to key in the entire
graph. - The group must write a program to solve THREE problems:
a. Function 1:
Check if the graph is strongly connected. If it is not, generate random edges*
between random cities until the graph is strongly connected. Print the
resulting graph.
b. Function 2:
Check if the graph has a cycle. If it is not, generate random edges* between
random cities until the graph has a cycle. Print the resulting cycle.
c. Function 3:
Allow the user to select two vertices and compute the shortest path between
the vertices. If there is no path between the selected vertices, generate
random edges* between random cities until the path exists. Print the shortest
path.
d. Include an additional function to RESET the graph to default.
e. Include an additional function for the user to REMOVE EDGES of their
choice. - Any new edges that are added must have the correct distance between two
particular cities. E.g., if an edge is created between Dhaka, Bangladesh and
Kuala Lumpur, Malaysia, it should be around 2587km. - Graphs that have been modified by any of the functions can be further modified by
other functions. Do NOT reset the graph after each function. The graph will only reset
if the program is closed or the reset function is used. - The group can implement ANY algorithm to solve the problems.
- Each member must be assigned ONE problem to solve.
Wiki Specifications
Please see appendix for tips on how to use the Wiki and some sample pages. There is no
specific format for the wiki but it MUST contain the following information:
a. Font: You can use any of the default eLearn fonts. For font size, preferably use
“Medium”for regular text and“Extra Large”for headings.
b. Please include navigation buttons or links to go back to your main page.
c. Front Page indicating division of tasks. Please include names, photos of your
members, matric number and the problem being solved. Suggestion:
a. Member 1 – Strong connectivity
b. Member 2 – Cycle detection
c. Member 3 – Shortest path
d. Description and justification of the chosen data structure and graph functions.
Cite the source (website) where the functions were taken from.
e. Description of how all the problems were solved. Use flowcharts to aid your
explanations.
Please do not copy/paste your source code into the report
f. Results:
a. Video recording to highlight the features and functionalities of your program.
Please upload the video to YouTube, Youku or any other video hosting
website and embed/include the link in Wiki. Please do not attach the file
there.
b. You can record 3 separate videos for each problem or 1 video for the whole
group.
c. Provide a discussion (in the wiki) of the results to accompany your video.
Highlight what was achieved, errors, problems, etc.
g. Please refer to the grading rubrics to ensure you fulfilled all requirements
Rubric (100%) – LO2/PO2
Category Weak Average Good
Data structure (Group) No specific data structure
was implemented
(0-1%)
A data structure was chosen
for the problem
(2-3%)
A suitable data structure
was chosen for the problem
with proper justifications
(4-5%)
Graph functions (Group) Minimal graph functions
were implemented, or the
functions were
implemented in an ad-hoc
manner
(0-2%)
A workable set of graph
functions were
implemented and used in all
the searching algorithms
(3-5%)
An efficient set of graph
functions were
implemented and used in all
the searching algorithms
with proper justifications
(6-10%)
Algorithm description
(Individual)
Flowchart and discussion
indicate a lack of
understanding of the
algorithm
(0-10%)
The basic idea of the
algorithm is apparent in the
flowchart and discussion
(11-20%)
Flowchart is easy to
understand and in-depth
discussion available
(21-30%)
Algorithm results
(Individual)
Algorithm produces wrong
results or has errors
(0-10%)
Algorithm is functioning
but cannot add random
edges
(11-20%)
Algorithm is functioning
and implemented well
(21-30%)
Creativity
(Individual)
Only basic functionality is
present
(0-2%)
Additional features have
been included into the
function
(3-5%)
Additional features or
modifications have been
made to the basic algorithm
(6-10%)
Overall Wiki (Group) Badly written and
structured
(0-5%)
Reasonable language and
structure
(6-10%)
Well-written and structured
(11-15%)
Appendix
A. Editing/Creating New Pages
First, select your group from the list:
To edit the wiki, click on the“Edit”button.
The main page must at least contain group information and some form of table of contents.
To create a new page, just include the page name in double square brackets. Example
[[This is a new page]]:
The link will be red if the page is yet to be created. Click on it to create the new page.
Use HTML format and click on“Create page”. The new page will be successfully created!
B. Adding Navigation/Hyperlinks
To add links to any pages in the wiki, all you need to do is to copy the URL of the page and
create a hyperlink. You can view all the pages in the wiki under“Map”.
Right click, copy the link address and use it to create your hyperlinks.
First click on the Link button:
Paste your link.
Your link is now ready!
C. Other Features
You can leave comments on specific pages by using the“Comments”tab. Each page can
have its own comments.
You can track changes by using the“History”tab. You can even restore versions.
By including a YouTube URL when creating links, videos are automatically embedded
(remember this is not compulsory, you can just leave the link as well)
D. Other Sample Pages
WX：codehelp