Java Programming Assignment 2

Part A – Binary search tree

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 advanced 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

Requirements types
• Functional requirements (FRs) specify how the software must behave.
• Operational requirements (ORs) specify aspects such as efficiency.
• Developmental requirements (DRs) specify how your software must be developed. 

General requirements

DR1: All your programming must conform to “Java Conventions and Programming Guidelines” – see module Moodle site.

DR2: You must paste the source code of all your classes into your report, as text, not images. 

 

Requirements
Task 1
FR1: You must create a Java class called MemberBST that implements the interface IMemberDB.
DR3: 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 not 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.

Note: use String.compareTo to compare strings lexicographically. You can treat uppercase and lowercase as different. (Hash codes have no place in this assignment.) We recommend that you use composition and make your public methods of your class callmethods taking a node as parameter.
You can implement methods either iteratively or recursively. You must not implement the method remove by just building a new tree. You should use 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 template file).

DR4: The constructor for MemberBST 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). 

Task 2
DR5: You must make appropriate use of assertions (assert statements) to protect preconditions of the operations (they should be the same as those for Assignment 1). Remember to enable assertion checking for your project.

Task 3
DR6: 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), attempt to get the Member or attempt to remove the Member:
o the Member name;
o the sequence of nodes of the tree visited.
• Paste your log into your report.

General requirements

Task 4
DR7: You must devise a test plan for your implementation. Be sure to check (among many other cases). This must supplement the test plan from Assignment 1 by adding tests:
• 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

Task 5
DR8: By using the supplied main program as in Assignment 1, or by other means, you must test your MemberBST.Include your test plan, test data used, expected results and actual results in  your report. You must show your actual results and the logging information copied from your log file or the output pane of your IDE. Do not simply state “test passed”, or similar – show evidence

Task 6
DR9: You must state 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 and compare it with the hash table.

General requirements

DR1: All your programming must conform to “Java Conventions and Programming Guidelines” – see module Moodle site.

DR2: You must paste the source code of all your classes into your report, as text, not images.

DR3: 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
FR1: 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.

Task 2
DR4: You must make appropriate use of assertions (assert statements) to protect preconditions of the operations. Remember to enable assertion checking for your project.

Task 3
FR2: You must write Java methods (as in Appendixes) to perform a depth-first traversal from a given node the network called cornwall and in your network, making use of the algorithm given in the appendix. Include the method’s text and the resulting sequence of node names in your report.

You must use the provided classes: ListInt.java, QueueInt.java, SetInt.java and StackInt.java.

Task 4
FR3: You must write Java methods (as in Appendixes) to perform a breadth-first traversal from a given node the network called cornwall and in your network, making use of the algorithm given in the appendix. Include the method’s text and the resulting sequence of node names in your report.

You must use the provided classes: ListInt.java, QueueInt.java, SetInt.java and StackInt.java

Task 5
FR4: You must implement Dijkstra’s algorithm (as in Appendix) making use of the data structures you have constructed, to find and display the shortest path between two stations in the network called cornwall and in your network. You must also ‘instrument’ your implementation to count the number of iterations of the while loop. 

You must use the provided classes: ListInt.java, QueueInt.java, SetInt.java and StackInt.java.
Show these results in your report. 

Task 6
FR5: You must implement the A-star algorithm (“A*”, as in Appendix) making use of the data structures you have constructed, to find and display the shortest path between two stations in the network called cornwall and in your network. Derive the f values from the coordinates of the stations and use of Pythagoras’ theorem. You must also ‘instrument’ your implementation to count the number of iterations of the while loop.

You must use the provided classes: ListInt.java, QueueInt.java, SetInt.java and StackInt.java.
Show these results in your report.

Task 7
DR5: Explain the difference in performance between Dijkstra’s algorithm and A* algorithm and state how their behaviour differ in the cases of cornwall and your network.

Task 8
DR6: Comment on the degree of success you have achieved with each of these tasks.