22C:21: Computer Science II: Data Structures
Problem Set 1. Posted 1/18
Notes: Problem 1 is your
homework and it is due in your discussion section meetings on Thursday, 1/25.
Of the remaining two problems, one will be solved by your TA
in the discussion section meetings on Thursday 1/25.
The remaining problem will be your quiz; this will occur at the end of
the discussion section meeting (on 1/25), you will have 20 minutes for
the quiz and you are allowed to consult your notes and textbook.
Part (1) of Problem 1 has been slightly changed.
You'll see the change in red.
All problems in this problem set pertain to the
Modify the RecordDB class in the following way, to permit
more code reuse and to increase efficiency.
What to submit: Use the submit tool to electronically
submit a single java file: RecordDB.java.
Here are instructions for using the
The current implementation of the RecordDB class is static
in the sense that a maximum size of the array is assumed to be known
apriori and the class does not deal with the possibility that
a new record might have to be inserted into a full array.
Reimplement the RecordDB class so that it is dynamic.
Specifically, you can still start with a size-20 array, but the
insert function should check if the array is currently full
and if so make it larger before inserting the new record.
Thus the maxRecords variable would no longer be static and
could have different values for different instances of the class.
You will see that "expanding" the array is a costly operation and
should be avoided as much as possible.
To minimize the number of expansions and at the same time not have too much
unused space, it makes sense to double the size of the array, each time
it needs to expand.
This is what you should implement as part of the insert function.
Implement a function called payRangeQuery that takes two
double parameters low and high and returns
all records of employees whose pay is between
low and high.
The collection of matching records should be returned
in an array whose size is exactly equal to the number of records in
The payRangeQuery function should be implemented as a
public method in the RecordDB class.