CSCI 262 Data Structures--Spring 2004

    Assignment 7

    Due at the beginning of class, Friday, April 2, 2004

    Home | | Syllabus | | Assignments | | Lecture Notes

    Programming Style: You will be graded not only on whether your programs work correctly, but also on programming style, such as the use of informative names, good comments, easily readable formatting, and a good balance between compactness and clarity (e.g. do not define lots of unnecessary variables, or write multiple statements to perform a task that can be expressed clearly in a single statement.) Create appropriate functions for tasks that can be encapsulated.

    Part 1: A new search function.

    A. Do problem P1 on page 297 of the textbook. It is restated here. Write a "ternary" search function (named ternary()) analogous to binary_search_2 that examines the key one-third of the way through the list, and if the target key is greater, then examines the key two-thirds of the way through, and thus in any case at each pass reduces the length of the list by a factor of three. Compute the index of the position one third of the way along the list using the formula:

    one_third = (bottom + (top - bottom)/3).

    Compute the index of the item 2/3 of the way along the list as follows:

    two_thirds = (bottom + 2*(top-bottom)/3).

    B. Include your function as an option in the testing program, (as we did with BS1 and BS2 in lab8), and examine its performance. Test the average number of comparisons made for successful and unsuccessful searches of lists of length 5, 10, 20, 100, and 1000. Write out the results in a table on a separate sheet and hand it in with this assignment. The search_compare.cc program is found in:

      ~csci262/assignments/assign7

    Modify the main() function of the search_compare program to accept a list length provided by the user for testing.

    C. Draw the comparison tree for a list of length 10. Use the convention used for the binary_search_2 tree developed in class.

    Part 2: Asymptotic analysis

    Do exercises 7.6 E2 and E15 on pages 312 - 314 of the textbook.

    Show your work and explain your answers.

    What to turn in:

    • A hard copy of the search_compare.cc modified to include the ternary() function.
    • Submit the soft copy of your program using the command:
      ~csci262/bin/submit csci262 assign7
    • A table of the average number of comparisons that ternary() does for the list lengths specified above.
    • A comparison tree for the ternary() function for a list of length 18
    • The answers to the problems listed in part 2.

    Home | | Syllabus | | Assignments | | Lecture Notes

    Constance Royden--croyden@mathcs.holycross.edu
    Computer Science 262--Data Structures
    Date Created: March 22, 2002
    Last Modified: March 22, 2003
    Page Expires: January 14, 2004