CHC5223 Data Structures and Algorithms Assignment 2: Binary search tree, graphs and pathfinding
CHC5223 Data Structures and Algorithms 2022–2023 Semest er 2 Assignment 2 Value 65% of coursework : Part A is 3 5% and Part B is 30% Individual work Learning outcomes Students will be able to understand 1.1 Data structures 1.2 The applications of data structures 1.3 Object -oriented programming concepts 1.4 Methods for program testing Students will have acquired skills in: 2.1 Data abstraction 2.2 The use of data structures 2.3 Programming at a more a dvanced level in a high -level object -oriented language 2.4 Program testing and documentation Students will have acquired skills in: 3.1 Self-management 3.2 Learning 3.3 Communication 3.4 Problem solving 3.5 Information technology
Process and what submit to Student Website The assignment submitted should compressed into a .zip file, the following files should be contained in the compressed file ： • a report as a Microsoft Word document containing text of all your classes. filename format: 12345678_CHC5223_CW 2_Report.docx • a .zip file containing the project: the runnable jar file (if available) and all the program’s source texts (.java ), including those provided filename format: 12345678C HC5223 CW2_Files.zip
Part A – binary search tree General requirements All your programming must conform to “ Java Conventio ns and Programming Guidelines” – see module Moodle site. You must paste the source code of all your classes into your report , as text or images . Introduction The topic of this part of the assignment is binary search trees . The interface IMember DB describe s methods for an abstract data type (ADT) which holds a database of Member objects. You must implement IMember DB as a binary search tree for Assignment 2 . You must not make any changes to these interfaces.
Task 1 You must c reate a Java class called Member BST that implements the interface IMemberDB . You must use a binary search tree but it does not need to be self-balancing . You must not encapsulate existing implementations of collections in your submission. For example, you must n ot create a TreeMap object and call methods on that object from your class. Failure to comply with this will result in zero marks for that part. Tip: use String.compareTo to compare strings lexicographically. You can treat uppercase and lowercase as different. (Hash codes have no place in this assignment.) Methods can be implemented either iteratively or recursively. You must not implement the method remove by just building a new tree . You m ay make use of the supplied source text for the method remove , based on Object -Oriented Programming in Oberon -2, Hanspeter Mössenböck Springer -Verlag 1993, page 78, transcribed into Java by David Lightfoot (see Appendix) . The constructor for Member BST must print the string “Binary Search Tree ” to System.out . Take care that you have not used a linear search O(n) where you should have used a binary search tree , aiming towards O(logn ). 12 marks
Task 2 You must make appropriate use of assertions ( assert statements ) to protect preconditions of the operations . Remember to enable assertion checking for your project . 2 mark s
Task 3 You must make your class log monitoring information, either to a text file or by calls of System.out.println . It must log (at least) : • for every addition of a Member (put), for every get the Member (get), for every deletion of a Member (remove ): o the Member name ; o the sequence of nodes of the tree visited . • Paste your log into your report. 6 marks We have supplied a main program CHC5223 .java for your use with this assignment . The name of the file is set in the static variable filename . Sample files sampleMembersUK.c sv and sampleMembersUS.csv each contain 500 members in this format.
Task 4 You must devise a test plan for your implementation . Be sure to check (among many other cases). • that deleting a leaf node works correctly • that deleting a node with one descendant works correctly • that deleting a node with two descendants works correctly 5 marks
Task 5 By using the supplied main program , or by other means , you must test your Member BST. Include your test plan, test data used, expected results and actual results in your report. You must show you r actual results and the logging information copied from your log file or the output pane of your IDE . Do not simply state “test pass ed”, or similar – show evidence 6 marks
Task 6 You must s tate honestly which of the requirements of Assignment 2 you have successfully fulfilled , citing evidence . Also , comment on the time efficiency and space efficiency of your implementation of the binary search tree . 4 marks total 35 marks CHC5223 Data Structures and Algorithms 2022–2023 Semest er 2 4 of 14 Part B – graphs and pathfinding The topic of this part of Assignment 2 is graphs and pathfinding . General requirements All your programming must conform to “ Java Conventio ns and Programming Guidelines” . You must paste the source code of all your classes into your r eport , as text, not images . You must implement all necessary data structures using only arrays When programming in Java it is usual to make use of collection classes from the Java class library. However, if you need to program in some other language such classes, or their equivalents, will not necessarily be available. Task 1 Find or devise a transport network – it need not be real, but it must be realistic. It must be an undirected, connected graph, with no loops. It must have at least eight nodes. Each node should have a name (with no spaces in it) and x and y positions (0 x < 256 and 0 y < 256) indicating the approximate position of the node on a map with a 256 × 256 grid ( y increasing downwards). The links must contain information about the distance between the nodes it connects. The distance can be measured in suitable units of length, such as km, or time, such as minutes. The links between them must be such that there are several pairs of nodes that are linked by more than one route. You m ust s ketch your network and include it in your report. The sketch must show each node annotated with its name and located on the sketch at its x and y position. The sketch must show each link annotated with its distance. You can make the sketch by hand but if you do so you will need to scan it to include in your report. 2 marks
Task 2 You must express your network as a text file using the syntax: “station” name x y “link” station station distance Each station must have been defined in a station line before being cited in a link line. Include the content of the text file in your report. 2 mark s
Task 3 You must implement Java classes StackInt , QueueInt , ListInt and SetInt . These will be subclasses respectively of abstract classes AbsStackInt , AbsQueueInt , AbsListInt , AbsSetInt , whose source is provided and shown in the appendixes . These are given as abstract classes (to be ‘sub -classed’) rather than as interfaces (to be ‘implemented’) partly because they are all ‘bounded’, that is, with limited capacity becau se of being implemented by arrays, and also to allow us to give you hints on how to implement them. CHC5223 Data Structures and Algorithms 2022–2023 Semest er 2 5 of 14 The required behaviour of the methods of the classes is indicated as pre - and post -conditions in comments . 4 marks Task 4 You must make appropriate use of assertions ( assert statements ) to protect preconditions of the operations . Remember to enable assertion checking for your project . 1 mark Task 5 By using JUnit or otherwise you must test your implementations of StackInt , QueueInt , ListInt and SetInt . To do this, create objects of each class in which capacity is set to a low value, such as
- You will set it to something larger when deploying the classes later. Include your test plan, test data used, expected results and actual results in your report. You r actual results must be shown either as screen images or as text copied from the output pane of the development toolkit . 4 marks Task 6 You must create a Java class StationInfo to implement the Java interface IStationInfo (supplied). 1 mark Task 7 You must create a Java class to define an adjacency matrix final double NO_LINK = Double.MAX_VALUE; // was erroneous double.MAX_VALUE int numStations; // 0 <= numStations <= capacity
double distance[ ][ ]; where, for all i, j in 0 <= numStations <= capacity distance [i][j] is the distance from station with number i to station with number j distance [i][j] is equal to distance [j][i] distance [i][i] = NO_LINK
Task 8 and also define a list of objects of class StationInfo held in an array.
Task 9 You must create a Java method in this class that reads a text file containing the textual description of your network and builds the corresponding list of stations and the matrix of links. You must p erform as many validity checks in this as you can and report any errors. Include the text of this class in your report. 2 marks
CHC5223 Data Structures and Algorithms 2022–2023 Semest er 2 6 of 14 Task 10 Use print statements to show the contents of the list and of the matrix after using your program to build them from the data held in your text file. Copy the results into your report. 2 marks
Task 11 You must write Java methods (as in Appendixes ) to perform a depth -first traversal from a given node of your network and a breadth -first traversal from the same node, making use of the algorithms given in the appendix. Include the methods text and the resulting sequence of node names in your report. 4 marks
Task 12 You must i mplement Dijkstra’s algorithm (as in Appendix ) making use of the data stru ctures you have constructed , to find and display the shortest path between two stations in your network . You must also ‘ instrument’ your implementation to count the number of iterations of the while loop 4 marks
Task 1 3 Explain the difference between Dijkstra’s algorithm and A* algorithm and state h ow their behaviour would differ in the case of your network . 2 marks
Task 1 4 Comment on the degree of success you have achieved with each of these tasks. 2 marks total 30 mark s
Obtaining help It is always permissible to request advice on what is required for this assignment . Please try to do this during normal contact time and avoid asking for such help in the last week before the deadline. You can discuss the requirements and the material covered in the assignment with others but what you create must be all your own work. Be careful to avoid collusion. Declare in your report any help you have received other than that from the module teachin g team. Feedback In addition to the written feedback that we aim to provide within the normal interval , you will be able to obtain fast, brief , verbal formative feedback and help on correcting you r work at your practical classes.
