CSci351 Introduction to File Processing: Homework 3

Due date: Wednesday, March 19, 2008 in class
Each homework may have a different weight, which is based on its difficulty level.
Absolutely no copying others' work
    1.     (20%)
    1. How many comparisons would be required on the average to find a record using sequential search in a 300,000-record disk file?


    2. If the record is not in the file, how many comparisons are required?


    3. If the file is blocked so that 40 records are stored per block, how many disk accesses are required on average?


    4. What if only one record is stored per block?



  2. In our discussion of the uses of relative record numbers (RRNs), we suggest that you can create a file in which there is a direct correspondence between a primary key, such as membership number, and RRN, so we can find a person's record by knowing just the name or membership number.     (25%)
    1. What kinds of difficulties can you envision with this simple correspondence between membership number and RRN?







    2. What happens if we want to delete a name?







    3. What happens if we change the information in a record in a variable-length record file and the new record is longer?







  3. Suppose a file must remain sorted. How does this affect the range of placement strategies available?     (15%)











  4. Why do placement strategies make sense only with variable-length record files?     (10%)











  5. Compare the average case performance of binary search with sequential search for a file of 10,000 records, assuming     (30%)
    1. That the records being sought are guaranteed to be in the file,





    2. That half of the time the records being sought are not in the file,





    3. That half of the time the records being sought are not in the file and that missing records must be inserted, and





    4. If the records are blocked with 40 records per block.