Homework answers / question archive / Homework # 8 In this assignment, we will return to our financial examples and implement a Bank ADT, in which a bank is a container of accounts

Homework # 8 In this assignment, we will return to our financial examples and implement a Bank ADT, in which a bank is a container of accounts

Computer Science

Share With

Homework # 8
In this assignment, we will return to our financial examples and implement a Bank ADT, in
which a bank is a container of accounts.
Use this link to accept the assignment:
https://classroom.github.com/a/q4mfCn58
1 The Binary Search Tree Data Structure
Please read section 9.5 in the textbook for a description of the binary search tree data structure.
In the textbook (as well as some online sources), a separate BTNode class is used; we will not do
that. Use a nested node classes as before.
Linked lists and arrays support insertion, removal or finding an entry in time proportional to the
number of entries in the container. Trees, on the other hand, offer a significant efficiency advantage
in that they generally support these operations in time proportional to the log of the number of
entries (assuming the tree is kept balanced).
In order to achieve the potential time efficiency of binary search trees, one needs to keep the
tree roughly balanced. In CompSci 535, you will learn some of the techniques used to do this (as
it happens, the tree-based containers in Java’s libraries use “red-black” trees). But in this course,
we will ignore the problems of unbalanced trees. Do not make any attempt to re-balance your tree.
The efficiency tests we run will make sure to construct a balanced tree.
2 Concerning the Bank ADT
A Bank is a container for customer accounts, accessed by their identification “number.” When a
customer opens an account, they provide a proposed account number, but if that is already in use,
the bank adds random digits as needed to get a fresh (unique) account number. Similarly, if the
number is too short, random digits are added (recall that that the string of numbers must have
at least four digits, as defined as Account.MIN_ACCOUNT_ID). You can create a random digit by
running random.nextInt(10) and then converting or adding the result to a string.
The bank provides only one way to examine accounts: an audit. The audit is started with an
optional identification “number,” and proceeds as long as there are still account remaining and the
auditor indicates they are still interested in continuing.
In other words, there are a very limited number of public operations:
Bank() Initialize a bank with no accounts.
open(owner,id,min,init) Open a bank account for the given owner, suggested id, minimum
balance and initial balance. Return the account.
audit(Auditor,id) Start an audit at the given identification number, The auditor will be
called on each account that comes at or after the given id, until the auditor returns false.
The auditor must be an instance of a class that implements the Auditor interface.
The binary search tree order is not numerical but rather by lexicographic order (string compar-
isons). For example "13" comes after "128" and before "130". The same order is used for audits.
Spring 2023 page 1 of 3CS 351: Data Structures & Algorithms Homework #7
A nice feature of lexicographic order is that a prefix always comes directly before anything with
that prefix.
You can implement the open method recursively or non-recursively. If you use recursion, you
may find it convenient to send an extra array argument is to record the newly created account.
The audit method should be implemented with a recursive helper method. At the basic level,
before we implement the extra features (starting and stopping part-way through), the code should
be a recursive in-order traversal (as described on pages 487–488, or pp. 477–478 in the 3rd edition).
But you should avoid the micro-management that the textbook uses. Use the following code as a
model:
private void inorderPrint(Node r) {
if (r == null) return;
inorderPrint(r.left);
System.out.println(r.data);
inorderPrint(r.right);
}
3 Concerning the BankAdditions class
The Bank ADT has a very limited number of operations, but some additional operations can be
implemented using the audit mechanism. The BankAdditions class is a wrapper class that provides
four additional operations:
count() Return the number of accounts at the bank.
getAccount(id) Return the account with the given id.
netAssets() Compute the net assets of the bank as a whole.
getBalanceSum(prefix) Compute the sum of all the balances of accounts with a given prefix
(perhaps owned by the same owner, so we don’t check that).
All these operations can be implemented using only the audit method of the bank. They do
not need to (and must not) access the data structure of the bank directly. You are given the
implementation of count to demonstrate how one can do this. The remaining three operations are
left to you to complete.
4 What You Need To Do
We recommend that you follow the following sequence of actions:
1. Define the Node class and data structure for Bank.
2. Get the BST invariant helper method and “wellFormed” working. Use TestInternals to
make sure this is done correctly. You will need to use recursion.
3. Unlock all the tests for the ADT and its wrapper.
4. Implement the “open” method and pass the first few tests (test0n) in TestBank.
5. Implement audit as a recursive in-order traversal that (for now) ignores the starting value and
requests by the auditor to stop the process. Pass the next set of tests (test1n in TestBank).
Spring 2023 page 2 of 3CS 351: Data Structures & Algorithms Homework #7
6. Update the audit code to handle an early termination (without throwing an exception). Pass
the next set of tests (test2n in TestBank).
7. Complete the audit code so that it can start at an arbitrary point. Choose a design that
is efficient: it goes straight down the tree to the starting point, rather than traversing, but
ignoring accounts, from the start. You should be able to pass the remaining tests in TestBank.
8. Confirm that the first set of “additions” tests (testCx in TestBankAdditions) works for
count.
9. Implement the remaining methods in BankAdditions to use an auditor to complete their task.
Each task will need a different class of auditors. Your should be able to pass the remaining
tests in TestBankAdditions.
10. Ensure that your algorithms are efficient with the efficiency tests. The tests are somewhat
slower than in previous assignments. They should take less than a minute in total to complete.