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 Record.java and RecordDB.java classes.

  1. 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 submit tool.

  2. 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.

  3. 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 collection. The payRangeQuery function should be implemented as a public method in the RecordDB class.