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.
• Write a search function that is similar to the currently implemented search function, except that the new search function returns an integer. If the given ssn is found, then the function returns a non-negative integer that is the index of the slot in which the ssn was found. If the given ssn is not found, then the function should return a negative integer, whose magnitude (absolute value) is one more than the index of the slot in which the ssn would have been found, had it been in the array. For example, if the social security numbers in the array are: 10, 20, 30, 40 and we were looking for 22, then the function should return -3 because if 22 were present in the array it would be in slot 2.

This new search function should produce no output.

• Reimplement the old search function (with the same functionality as before) so that it just calls the new search function and produces appropriate output.

• Reimplement the insert and delete functions so that they call the new search function. You would have noticed that both insert and delete currently perform a linear scan of the array; insert does it in order to find a slot to insert the new record in and delete does it in order to find the record with the given ssn. Having implemented the new search function, it is possible to simplify and speed-up both insert and delete by making appropriate calls to the new search function.

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.