” CPT212编程设计 写作、 辅导Python程序PUSAT PENGAJIAN SAINS KOMPUTER(School of Computer Sciences)CPT212- Design and Analysis of AlgorithmsAssignment II: Graph AlgorithmsRelease Date: 17th May 2021 (Monday)Due Date: 20th June 2021 (Sunday) by 11:59pm sharpObjectivesThe purpose of this assignment is to test your understanding of graph representation andalgorithms. You will be Required to code the actual algorithms to solve problems that havebeen discussed in class.Prerequisites1. Each group must consist of 3 individuals.2. Each group will have ONE wiki to document the functionality of their program.3. Each group must produce a ONE cohesive program (one source file or project file).4. You can choose to code in Python or C/C++ but choose only ONE.5. Please specify instructions on how to run your codes.6. You can use algorithms/codes from online sources to solve the given problems butmust be cited.7. Although this is a group project, a large percentage of the grade will be individualwork (70% individual, 30% group).Default Graph1. Go to httpss://randomcity.net/ and pick 5 random cities and their correspondingcountries.2. Go to httpss://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).3. Between each city, add only one directed, weighted edge.4. Example graph (you cannot use the exact same one):Instructions1. Choose ONE data structure to represent the graph (E.g., adjacency list, adjacencymatrix or incidence matrix).2. There must be a list of common graph functions (E.g., add new edge, remove edgeetc.). These functions must be used to modify the graph.3. The same data Structure and functions must be used by every group member.4. Each time the program starts up, the default graph must be already initialized andcan be modified by any of the functions. Do NOT prompt the user to key in the entiregraph.5. 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 theresulting graph.b. Function 2:Check if the graph has a cycle. If it is not, generate random edges* betweenrandom 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 betweenthe vertices. If there is no path between the selected vertices, generaterandom edges* between random cities until the path exists. Print the shortestpath.d. Include an additional function to RESET the graph to default.e. Include an additional function for the user to REMOVE EDGES of theirchoice.* Any new edges that are added must have the correct distance between twoparticular cities. E.g., if an edge is created between Dhaka, Bangladesh andKuala Lumpur, Malaysia, it should be around 2587km.6. Graphs that have been modified by any of the functions can be further modified byother functions. Do NOT reset the graph after each function. The graph will only resetif the program is closed or the reset function is used.7. The group can implement ANY algorithm to solve the problems.8. Each member Must be assigned ONE problem to solve.Wiki SpecificationsPlease see appendix for tips on how to use the Wiki and some sample pages. There is nospecific 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 useMedium 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 yourmembers, matric number and the problem being solved. Suggestion:a. Member 1 Strong connectivityb. Member 2 Cycle detectionc. Member 3 Shortest pathd. 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 yourexplanations.**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 hostingwebsite and embed/include the link in Wiki. Please do not attach the filethere.b. You can record 3 separate videos for each problem or 1 video for the wholegroup.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 requirementsRubric (100%) LO2/PO2Category Weak Average GoodData structure (Group) No specific data structurewas implemented(0-1%)A data structure was chosenfor the problem(2-3%)A suitable data structurewas chosen for the problemwith proper justifications(4-5%)Graph functions (Group) Minimal graph functionswere implemented, or thefunctions wereimplemented in an ad-hocmanner(0-2%)A workable set of graphfunctions Wereimplemented and used in allthe searching algorithms(3-5%)An efficient set of graphfunctions wereimplemented and used in allthe searching algorithmswith proper justifications(6-10%)Algorithm description(Individual)Flowchart and discussionindicate a lack ofunderstanding of thealgorithm(0-10%)The basic idea of thealgorithm is apparent in theflowchart and discussion(11-20%)Flowchart is easy tounderstand and in-depthdiscussion available(21-30%)Algorithm results(Individual)Algorithm produces wrongresults or has errors(0-10%)Algorithm is functioningbut Cannot add randomedges(11-20%)Algorithm is functioningand implemented well(21-30%)Creativity(Individual)Only basic functionality ispresent(0-2%)Additional features havebeen included into thefunction(3-5%)Additional features ormodifications have beenmade to the basic algorithm(6-10%)Overall Wiki (Group) Badly written andstructured(0-5%)Reasonable language andstructure(6-10%)Well-written and structured(11-15%)AppendixA. Editing/Creating New PagesFirst, 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/HyperlinksTo add links to any pages in the wiki, all you need to do is to copy the URL of the page andcreate 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 FeaturesYou can leave comments on specific pages by using the Comments tab. Each page canhave 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请加QQ：99515681 或邮箱：99515681@qq.com WX：codehelp
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
