Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Hand-in Instructions
Go to COMP2140 in UM Learn; then, under “Assessments” in the navigation bar at the top, click on
“Assignments”. You will find an assignment folder called “Assignment 5”. Click the link and follow the
instructions. Please note the following:
Submit the ONE .java file that you are completing only. The .java file must contain all the source code
that you wrote. The .java file must be renamed A5<your last name><your first name>.java (e.g.,
A5CameronHelen.java).
Please do not submit anything else.
We only accept homework submissions via UM Learn. Please DO NOT try to email your homework
to the instructor or TA or markers — it will not be accepted.
We reserve the right to refuse to grade the homework or to deduct marks if you do not follow instructions.
Assignments become late immediately after the posted due date and time. Late assignments
will be accepted up to 49 hours after that time, at a penalty of 2% per hour or portion thereof. After
49 hours, an assignment is worth 0 marks and will no longer be accepted.
How to Get Help
Your course instructor is helpful: For our office hours and email addresses, see the course website on
UM Learn (on the right side of the front page).
For email, please remember to put “[COMP2140]” in the subject and use a meaningful subject, and to
send from your UofM email account.
Course discussion groups on UM Learn: A discussion group for this assignment is available in the
COMP 2140 course site on UM Learn (click on “Discussions” under “Communications”). Post questions
and comments related to Assignment 5 there, and we will respond. Please do not post solutions, not even
snippets of solutions there, or anywhere else. We strongly suggest that you read the assignment discussion
group for helpful information.
Computer science help centre: The staff in the help centre can help you (but not give you assignment
solutions!).
php for location and hours. You can also email them at [email protected].
Programming Standards
When writing code for this course, follow the programming standards, available on this course’s website on
UM Learn. Failure to do so will result in the loss of marks.
1
Question
Remember: You will need to read this assignment many times to understand all the details of the code
you need to write.
Goal: To compare the execution of insertions and searches in binary search trees (BSTs) and in leaf-based
2-3 trees.
Code you can use: You are permitted to use and modify the code your instructor gave you in class for
BSTs and their nodes, and for leaf-based 2-3 trees and their nodes. You are NOT permitted to use code from
any other source, nor should you show or give your code to any other student. Any other code you need for
this assignment, you must write for yourself. We encourage you to write ALL the code for this assignment
yourself, based on your understanding of BSTs and leaf-based 2-3 trees — you will learn the material much
better if you write the code yourself.
This assignment is more like a lab than previous assignments were. File A5.java contains a nearly-complete
program that reads in sequences of integers. For each sequence, the program times each of the following four
steps:
Inserting the sequence of integers into an empty binary search tree, in the order that the integers occur
in the sequence.
Then, searching for each of the integers in the sequence in the binary search tree.
Inserting the sequence of integers into an empty leaf-based 2-3 tree, in the order that the integers occur
in the sequence.
Then, searching for each of the integers in the sequence in the leaf-based 2-3 tree.
After timing each of these steps, the program prints the number of elements in the sequence, the timing
information and first 20 elements in each tree in sorted order (or the whole tree if there are no more than
20 elements), and then moves on to the next sequence.
You need to write the bodies for all the methods in the BST class. The headers for the methods
and the BST node class are already provided — don’t change them. You can add private helper methods
to the BST class as needed.
You also need to write the bodies for methods in the TwoThreeTree class (details below).
The Nodes for the Leaf-Based 2-3 Tree
We have provided a private TwoThreeNode class inside the TwoThreeTree class. You may change or add
constructors, but note that doing this may cause the debugging methods to stop working. You may NOT
change any of the other already-written parts (details below). You are permitted to add more methods to
this class as needed.