Algorithms and Analysis COSC 1285/2123

Assignment 1:Implementing and Evaluating Data Structures for Maze Generation

Pleasereadallthefollowinginformationbeforeattemptingyourassignment. This is an individualassignment.You may not collude with any other person (or people) and plagiarise their work.Everyone is expected to present the results of their own thinking and writing.Never copy another student’s work (even if they “explain it to you first”) andnevergiveyourwrittenworktoothers. Keepanyconversationhigh-levelandnever show your solution to others.Never copy from the Web or any other resource or use Generative AI like ChatGPT togenerate solutions or the report.Remember you are meant to develop the solution by yourself - assessment is designed to encourage everyone tolearn,andyouarenotdoingyourselfanyfavoursbytakingshortcuts.Suspectedcases ofcollusionorplagiarismwillbedealtwithaccordingtoRMITAcademicintegrity policy.

In the submission (your PDF file for the report of Task B) you will be required to certify that the submitted solutionrepresents your own work onlyby including the following statement:

ClarificationtoSpecifications

Please periodically check the assignment FAQ for further clarifications about specifica- tions.In addition, the lecturer will go through different aspects of the assignment each week,soevenifyoucannotmakeittothelectorials,besuretocheckthecoursematerial page on Canvas to see if there are additional notes posted.

1. Overview

Inthisassignment,youwillimplementanumberofwell-establisheddatastructures for developing a maze generation program and evaluate their performance to determine whatwouldbethebestdatastructureindifferentsituations.Thisassignmentaimsto help crystallise the analytical parts of the course and familiarise you with certain data structures,howimplementationdecisionscanhaveaninfluenceonrunningtimes,and howtoempiricallyevaluatedifferentpossibledesignchoices(inthiscase,datastructures).

1. LearningOutcomes

Thisassessmentrelatesto3learningoutcomesofthecoursewhichare:

• CLO2:Compare,contrast,andapplykeydatastructures:trees,lists,stacks, queues, hash tables and graph representations;
  • CLO4:Theoreticallycompareandanalysethetimecomplexitiesofalgorithmsand data structures; and
  • CLO5:Implement,empiricallycompare,andapplyfundamentalalgorithmsanddata structures to real-world problems.

1. Background

Amazeistypicallya2Dgridofcellsandwalls,anentranceandanexit.Theaimis tofindapathfromtheentrancetotheexit.SeeFigure1foranexample.Thereare strategiesandalgorithmstosolveamaze,i.e.,findsuchasolutionpathgivenamaze. Therearealsostrategiesandalgorithmstogenerateamaze;inthisassignment,wewill focus on generation of mazes, however, the implementation for maze generation is already providedinthePythonskeleton(detailedinSection4)andyouwillneedtoonlyfocus ondatastructuresthatrepresentmazesinourmazegenerationscenario.

Wearefocusedonperfectmazes,wherethereisalwaysapathfromentrancetoexit (bythevirtuethatinaperfectmaze,thereisalwaysapathfromacellinthemazeto any other cell in the maze).In addition, in this assignment, we focus on 2D, square cell mazes,i.e.,eachcellhas4sides.Thereisnostandardwaytoreferencethecells,hence weadoptedtheconventionissuedinFigure1,with(0,0)denotingthebottomleftcell, andcolumnsincreaseaswetraveltotherightofthemaze(page),androwsincreasesas we travel up the maze (page).In order to specify the entrances and exits, we have added one row above, and one row below the maze, and one column to the left, and one columnto the right of the maze.This means the row below the maze is referenced as -1, the row aboveby5(ifwehave5rowsinthemaze),theadditionalcolumntotheleftofthemaze by-1,andthecolumntotherightby5(ifwehave5columnsinthemaze).Thisallows ustostillbeabletousetheoriginalindexing,i.e.,(0,0)referstothebottomleftcellof themaze,butstillabletoreferencethelocationofentrancesandexits.

1. Assessmentdetails

Theassignmentisbrokenupintoanumberoftasks,tohelpyouprogressivelycomplete the project.

Figure 1:Sample 5 by5 maze.The entrances are il- lustrated as arrows pointing towards the maze, and ex-its are illustrated as arrows pointing away from the maze. The cells of the maze are in- dexed from 0, and the row and column indices are drawn outside the maze.Note that the bottom left cell is (0,0), and top right cell is (4,4).This follows the convention that matplotlib follows (we use that for visualisation). Notetheentrancesarespec- ifiedas(0,-1)and(-1,1)and

exitsas(5,4)and(3,5).

Task A: Implement Mazes using Different Data Structures(6 marks)

Inordertogeneratemazes,weneedawaytorepresentthem.Intheassignmentand this task, you will implement a Maze abstract data type using graphs.Your task is to complete the implementation of a number of sections in the provided Python skeletoncode.The implementation of the maze using 2D arrays is provided as an example in the skeleton.

DataStructureDetails

Mazes can be implemented using a number of data structures.We provide the imple- mentationof2Darraysandyouarerequiredtoimplementtwoothers:

• 2DArray.Eachelementinthe2Darrayrepresentsacellorawallina2D(square, 4 sided, cell) maze.

You are required to implement the maze abstract data type using the following data structures:

• Graph (edge list).Edge list representation of a graph representing a 2D (square cell)maze.Anedgelistisasimplewaytorepresentagraph.Itconsistsofalist orarrayofalltheedgesinthegraph.Eachedgeisrepresentedasapairofvertices that it connects.
• Graph(incidencematrix).Incidencematrixrepresentationofagraphrepresenting a2D(squarecell)maze.Itisamatrixwhererowscorrespondtoverticesand

Figure2:Samplegraphswith4verticesand4edges.

columnscorrespondtoedges.Anentryinthematrixindicateswhetheravertexis

incidenttoanedge.

Example Consider the two graphs depicted in Figure 2.The edge list representation ofthese graphs are:

EG1={(A,B),(A,D),(B,C),(C,D)}

EG2={(A,C),(A,D),(B,C),(B,D)}

Andtheincidencematrixrepresentationsareasfollows:

CodeFramework

We provide Python skeleton code (see Table1) to help you get started and ensure we haveconsistentinterfacingtoruncorrectnesstesting.Table1alsoliststhefilesthatyou reallyneedtomodify/implement(inthedescriptioncolumn). Youneedtocompletethe implementationofedgeListGraph.pyandincidenceMatGraph.py.Wehaveprovidedthe code to construct and provide functionality of a maze in the graphMaze file.It is mostly generic, but does assume a certain way of implementing the maze using the two graph datastructures.Ifthatdoesnotalignwithyourapproach,pleasefeelfreetomodify

file                                                                                description

mazeTester.py                                                          Code that reads a configuration file then exe- cutes the generation using specified data struc- ture.No need to modify this file.

maze/maze.py                                                         Abstract class for mazes.All implementationsof a maze should implement the Maze class.No need to modify this file.

maze/util.py                                                              Coordinates class, and other utlity classes and methods.No need to modify this file.

maze/graph.py                                                        Abstract class for graphs. All graphimplemen- tations should implement the Graph class.No need to modify this file.

maze/arrayMaze.py                                               2D array data structure implementation ofa maze.No need to modify this file.

maze/graphMaze.py                                             Graph based data structure implementations of a maze.Modify if need to.

maze/edgeListGraph.py                                       Codethatimplementsanadjacentlist(for

maze).Completetheimplementation.

maze/incMatGraph.py                                          Codethatimplementsanadjacentmatrix(for maze).Complete the implementation.

maze/maze viz.py                                                 Modifiedcodeusedtovisualisegeneratedmazes using matplotlib.No need to modify this file.

generation/mazeGenerator.py                          Abstractclassformazegenerators.Noneedto

modifythisfile.

generation/recurBackGenerator.py                 Implementationoftherecursivebacktracking

mazegenerator.Noneedtomodifythisfile.

README.txt                                                              Pleasereadthisfirst,itmentionshowtorunthe code.No need to modify this file.

Table1:TableofprovidedPythonskeletonfiles.

it, but please ensure the same functionality is still maintained and that you are able to generate mazes.

Please note that the first time you run this implementation, the two provided configu-ration files will use the array data structure as the representation of the maze.If youmodify and use one of the configuration files intended for graphs, you may encountererrors because the graph implementations are currently incomplete.Don’t be alarmed by these errors as once the graph implementation is finalised, the program should be able to correctly output the graphs.

NotethatforTaskA,partoftheassessmentwillbebasedonautomatedtesting,which will feed a number of configuration files into your (completed) implementation of the provided Python skeleton.We will then check if the generated mazes are correct, e.g., whethertheyareperfect,havecorrectentrancesandexits,didn’tgointoinfiniteloops etc.Wewouldlikeyoutodosometestingaboutthis-ifyoulookatthecode,there

is a method to test if the generated maze is perfect which is not implemented.This implementationwon’tbepartofyourassessment,butitmightbeusefultoconsider how to implement it and perform checks yourself as part of practicing code evaluation. Remember a perfect maze is one where any cell in the maze can reach any other cell, or another way to put it, there exists a path between any pair of cells in the maze.If you implementsomethingtoevaluateperfectmazes,pleaserefrainfromsubmittingitaspart of your final code submission.

Notes

• Ifyoucorrectlyimplementthe“Implementme!”partsoftheprovidedskeleton,you donotneedtodoanythingelsetogetthecorrectoutputformatting.mazeTester.py will handle this.

• Wewillrunyourimplementationontheuniversity’scoreteachingservers,e.g.,

  titan.csit.rmit.edu.au,jupiter.csit.rmit.edu.au,andsaturn.csit.rmit.edu.au.

  If you develop on your own machines, please ensure your code compiles and runs onthesemachines.Discoveringatthelastminutethatyourcodedoesnotcompile on these machines is something you would want to avoid.If your code does not runonthesemachines,weunfortunatelydonothavetheresourcestodebugeach one and cannot award marks for testing.Please note this carefully, this is a firm requirement.

• All submissions should be compiled with no warnings on Python 3.6.8 when com- piling the files specified in Table 1 - this is the default Python3 version on the Core teachingservers.Pleaseensureyourcoderunsonthecoreteachingserversand withthisversionofPython.Pleasenotethiscarefully,thisisafirmrequirement.

TaskB:EvaluateyourDataStructures(12marks)

In this second task, you will evaluate your implemented structures both theoretically and empirically in terms of their time complexities for the different use case scenarios and different operations, e.g., removeWall().Scenarios arise from different parameter settings for generating a maze.

Write a report on your analysis and evaluation of the different implementations.Consider and recommend in which scenarios each type of implementation would be most appro- priate. The report should be 5 pages or less, in font size 12. See the assessment rubric (AppendixA)forthecriteriaweareseekinginthereport.

TheoreticalAnalysis

Atfirst,youaretoconductatheoreticalanalysisoftheperformance.Giventheheight handwidthw(intermsofnumberofrowsandcolumns)ofthegeneratedmaze,report the best case and worse case running time estimate in terms of the exact asymptotic complexity (Θ) of each of your graph implementations when executing updateWall() and neighbours().You will also need to provide an example scenario and explanation on thebestcaseandworsecaserunningtimeestimates.Thiswillhelpyouwhenexplaining yourempiricalanalysisresults.Puttheresultsinthefollowformatofatable:

EmpiricalAnalysis

Typically, you may use real usage data to evaluate your data structures.However, for this assignment, you will write configuration file generators to enable testing over different scenarios of interest.There are many possibilities, hence to help you we suggest you consider the following factors.

• Thedimensionsofthemaze.
• Datastructureimplementations.

Data GenerationWhen generating different maze dimensions, you may want to write someconfigurationfilegenerators(orgeneratordirectlywithinacopyofmazeTester.py). Due to the randomness of the data, you may wish to generate several datasets with the same parameters settings and take the average across a number of runs.

TaskC:VideoInterview(2marks)

Afterthereportandcodeissubmitted,youwillbeaskedtorecordyourresponsestoa number of questions in Canvas.These questions will ask you about aspects of your implementation or report.You will have a set time to consider the questions, make a recordingthenuploadthatrecording.Moredetailswillbeexplainedclosertothedue date.

1. ReportStructure

Asaguide,thereportcouldcontainthefollowingsections:

• Theoretical Analysis of Data Structures:In this section, perform a theoretical anal-ysis of the running time and complexities associated with different data structure implementations.RefertoSection4formoredetail.
  • Data and Experimental Setup Explanation:Describe your data and experimentalsetup.Briefly explain the parameter configurations used in your experiments, e.g.,therangeofmazedimensions.Provideinsightintowhyyouselectedsuchrange. You can use a paragraph or even a high-level pseudo code or figure.Also describe whichapproach(es)youdecidetouseformeasuringthetimingresults.

• Evaluation of Data Structures:Analyze, compare, and discuss the results obtained from evaluating the data structures using the generated data.Explain why you observed these results.Consider using the known theoretical time complexities of eachdatastructure’soperationstosupportyouranalysis.
  • Summary:Conclude by summarising your analysis and providing recommendations. For a given range of maze dimensions, suggest which data structure is most suitable, e.g., “for this range of maze dimensions, Irecommend to use this data structure because...”.Referbacktoyourpreviousanalysisforcontext.

PleasemakesuretoincludeyournameandstudentIDaswellasthestatementonthe firstpageofthisdocumentinyourreport.

1. Submission

Thefinalsubmissionwillconsistofthreeparts:

1. Your Python source code of your implementations.This must include all files, in- cluding the provided skeleton as well as any extra files you have created.Your source codeshouldbeplacedintothesamestructureasthesuppliedskeletoncode,and the root directory/folder should be named as Assign1-<your student number>. Specifically,ifyourstudentnumberiss12345,whenunzipAssign1-s12345.zip isexecutedthenallthesourcecodefilesshouldbeindirectoryAssign1-s12345. We use automated testing and compilation, and the testing script will expect this structure,soifisdifferent,thescriptmaynotbeabletocompileyourcode.So please make sure not to change the structure.
2. YourwrittenreportforpartBinPDFformat,called“assign1.pdf”.Placethis pdf within the Python source file directory/folder.
3. Your data generation code. Create a sub-directory/sub-folder called “dataGen” within the Python source file directory/folder.Place your data generation code within that folder.

The final folder (consisting the source code, report and dataGen subfolder) should be zipped up and named as Assign1-<your student number>.zip.E.g., if your student numbers is s12345, then your submission file should be called Assign1-s12345.zip, and when we unzip that zip file, then all the submission filesshould bein thefolder Assign1- s12345.

Note:submissionofthereportandcodewillbedoneviaCanvas.We will provide details regarding Task C closer to the submission deadline.

1. Assessment

Theprojectwillbemarkedoutof20.

Theassessmentinthisprojectwillbebrokendownintothreeparts.Thefollowingcriteria will be considered when allocating marks.

Implementation(6/20):

While the emphasis of this project is not on programming, we would like you to maintain decentcodingdesign,readabilityandcommenting,hencecommentingandcodingstyle will make up a portion of your marks.For a detailed breakdown of the implementation marks,pleaserefertotherubricavailableviaCanvas.

Report(12/20):

ThemarkingsheetinAppendixAoutlinesthecriteriathatwillbeusedtoguidethe marking of your evaluation report1.Use the criteria and the suggested report structure (Section4)toinformyouofhowtowritethereport.

VideoInterview(2/20):

Thisisapass/failassessment,andyou’llbeassessedbasedonyourabilitytoanswer some questions about the code and report.

LateSubmissionPenalty:Latesubmissionswillincura10%penaltyonthetotal marks of the corresponding assessment task per day or part of day late, i.e, 2 marks per day.Submissions that are late by 5 days or more are not accepted and will be awarded zero,unlessspecialconsiderationhasbeengranted.GrantedSpecialConsiderationswith new due date set after the results have been released (typically 2 weeks after the dead- line) will automatically result in an equivalent assessment in the form of a practical test, assessing the same knowledge and skills of the assignment (location and time to be ar- ranged by the coordinator).Please ensure your submission is correct (all files are there, compilesetc),re-submissionsaftertheduedateandtimewillbeconsideredaslatesub- missions. Toavoidsubmittinglate,makesuretocompleteandsubmityourassignments a bit ahead of the deadline, as the core teaching servers and Canvas can sometimes be slow.We strongly advice you submitat least one hour before the deadline.Late submissions due to slow processing of Canvas or slow Internet will not be lookedupon favourly,evenifitisafewminuteslate.SlowprocessingofCanvasorslowInternet willrequiredocumentationandevidencesubmissionattemptswasmadeatleastonehour before the deadline.

Assessmentdeclaration:Bysubmittingthisassessment,youagreetotheassessment

declaration-https://www.rmit.edu.au/students/student-essentials/assessment-and-exams/assessment/assessment-declaration

1. Academicintegrityandplagiarism(standardwarning)

Academic integrity is about honest presentation of your academic work.It means ac- knowledging the work of others while developing your own insights, knowledge and ideas. Youshouldtakeextremecarethatyouhave:

• Acknowledged words,data,diagrams,models,frameworks and/or ideas of others you have quoted (i.e.directly copied), summarised, paraphrased, discussed or men- tionedinyourassessmentthroughtheappropriatereferencingmethods

1Noteforthemarkingguide,ifoneofthecriteriaisnotdemonstrated,then0markswillbeawarded for that criteria.

• Provided a reference list of the publication details so your reader can locate thesource if necessary. This includes material taken from Internet sites. If you do not acknowledge the sources of your material, you may be accused of plagiarism because you have passed off the work and ideas of another person without appropriate referencing, as if they were your own.

RMITUniversitytreatsplagiarismasaveryseriousoffenceconstitutingmisconduct. Plagiarism covers a variety of inappropriate behaviours, including:

• Failuretoproperlydocumentasource
  • Copyrightmaterialfromtheinternetordatabases
  • Collusionbetweenstudents

Forfurtherinformationonourpoliciesandprocedures,pleaserefertothefollowing:https://www.rmit.edu.au/students/student-essentials/rights-and-responsibilities/academic-integrity.

1. GettingHelp

Therearemultiplevenuestogethelp.Thereareweeklyconsultationhours(seeCanvas for time and location details).In addition, you are encouraged to discuss any issues youhavewithyourTutor.WewillalsobepostingcommonquestionsontheAssignment1 FAQ section on Canvas and we encourage you to check and participate in the Ed Forum discussion forum.However, please refrain from posting solutions, particularly as this assignmentisfocusedonalgorithmicanddatastructuredesign.

A       MarkingGuidefortheReport