Design and Analysis of Algorithms

Assignment II: Graph Algorithms Release Date: 4th May 2020 (Monday) Due Date: 7th June 2020 (Sunday) by 12:00am 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 1. Each group must consist of 3 individuals. 2. Each group must submit ONE report. 3. Each group must produce a ONE cohesive program (one source file or project file). 4. Any programming language can be used but choose only ONE (Java, Python, C++). Note: For Java programs, please specify your Java version as well as IDE that has been used. 5. You can use codes from online sources to solve the given problems but must be cited. 6. Although this is a group project, a large percentage of the grade will be individual work (70% individual, 30% group). Default Graph The following digraph will be used as the default graph in this group project.

Instructions 1. Choose ONE data structure to represent the graph (E.g. adjacency list, adjacency matrix or incidence matrix). The same data structure and functions must be used by every group member. 2. 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. 3. The group must write a program with THREE functions: a. Function 1: Check if the graph is strongly connected. If it is not, generate random edges between random vertices 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 vertices 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 vertices until the path exists. Print the shortest path. d. Include an additional function to RESET the graph to default. 4. 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. 5. The group can implement ANY algorithm to solve the problems. 6. Each member must be assigned ONE function to code. Report Specifications There is no specific format for the report but it MUST contain the following information: a. Font: Times New Roman (10), Single-Spacing (1.0) b. Cover Page indicating division of tasks. Suggestion: a. Member 1 Strong connectivity b. Member 2 Cycle detection c. Member 3 Shortest path c. Description and justification of the chosen data structure and graph functions. Cite the source (website) where the functions were taken from. d. Description of how all the problems are solved. Use pseudocodes to aid your explanations. **Please do not copy/paste your source code into the report** e. Results: a. Screenshots of all outputs b. Explanation for the outputs f. Maximum number of pages: 15 pages excluding front page, references and appendices (You will be penalized 1% for each additional page)

6 AU 12 BE 1 9 EG HK 4 DK Rubric (100%) - LO2/PO2 Category Weak Data structure (Group) No specific data structure was implemented (0-1%) Graph functions (Group) Algorithm description (Individual) Minimal graph functions were implemented, or the functions were implemented in an ad-hoc manner (0-2% Pseudocode and discussion indicate a lack of understanding of the algorithm (0-10%) Algorithm produces wrong results or has errors (0-10%) Only basic functionality is present (0-2%) Average Good A data structure was chosen A suitable data structure for the problem was chosen for the problem (2-3%) with proper justifications (4-5%) A workable set of graph An efficient set of graph functions were functions were implemented and used in all implemented and used in all the searching algorithms the searching algorithms (3-5%) with proper justifications (6-10%) The basic idea of the Pseudocode is easy to algorithm is apparent in the understand and in-depth pseudocode and discussion discussion available (11-20%) (21-30%) Algorithm is functioning Algorithm is functioning but cannot add random and implemented well edges (21-30%) (11-20%) Additional features have Additional features or been included into the modifications have been function made to the basic algorithm (3-5%) (6-10%) Reasonable language and Well-written and structured structure (11-15%) (6-10%) Algorithm results (Individual) Creativity (Individual) Overall Report (Group) Badly written and structured (0-5% 6 AU 12 BE 1 9 EG HK 4 DK Rubric (100%) - LO2/PO2 Category Weak Data structure (Group) No specific data structure was implemented (0-1%) Graph functions (Group) Algorithm description (Individual) Minimal graph functions were implemented, or the functions were implemented in an ad-hoc manner (0-2% Pseudocode and discussion indicate a lack of understanding of the algorithm (0-10%) Algorithm produces wrong results or has errors (0-10%) Only basic functionality is present (0-2%) Average Good A data structure was chosen A suitable data structure for the problem was chosen for the problem (2-3%) with proper justifications (4-5%) A workable set of graph An efficient set of graph functions were functions were implemented and used in all implemented and used in all the searching algorithms the searching algorithms (3-5%) with proper justifications (6-10%) The basic idea of the Pseudocode is easy to algorithm is apparent in the understand and in-depth pseudocode and discussion discussion available (11-20%) (21-30%) Algorithm is functioning Algorithm is functioning but cannot add random and implemented well edges (21-30%) (11-20%) Additional features have Additional features or been included into the modifications have been function made to the basic algorithm (3-5%) (6-10%) Reasonable language and Well-written and structured structure (11-15%) (6-10%) Algorithm results (Individual) Creativity (Individual) Overall Report (Group) Badly written and structured (0-5%