CS 378: Information Systems

Spring 1999

Assignment 3

External Searching

Due Tuesday March 2

For this assignment, you will be defining two search member functions for the PageManager class that work with a sorted list of movie records. Both of these functions take a string as an argument and return a string consisting of all the records whose titles start with the given string. The first member function should perform a sequential search while the second should perform a binary search. Use the following prototypes in defining these member functions:

   string seqSearch(string key)
   string binSearch(string key)

In matching a title you may assume that the title starts in the 33rd position (index of 32). The returned string should consist of all matching records concatenated and separated by the newline character ('\n'), which is how they are stored in the database.

To test your member functions, create a driver program that loads the movie records and allows the user to repeatedly issue search keys. The driver program should then write out the list of matching records.

You may use either the original database code or the code you modified from the last assignment. To demonstrate that your program works correctly, monitor the number of I/O operations with each query. Compare the two search strategies and summarize your results in a one to two paragraph summary.

Submission

Please turn in hardcopies of the following:

• Any modified files with your modifications highlighted.
• A test script showing that your program works on a few queries.
• Your summary of the results.