**
Fill This Form To Receive Instant Help**

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.

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.