CSCI 132 Data Structures

    Assignment 7

    Due at the beginning of class, Friday, April 4, 2014

    Note: Because of the exam on 4/8, no late assignments will be accepted after Monday, 4/7, so that I can post solutions for you to study.

    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. You will need to provide a helper function, run_ternary( ) to initialize the parameters, as we did for BS1 and BS2 in lab8. You will find the search_compare.cc program along with associated list functions in:

      ~csci132/assignments/assign7

    You should copy these files into your own assignments directory.

    Please run the comparisons in the following order:

    1. Successful searches for Sequential search
    2. Successful searches for Ternary search
    3. Unsuccessful searches for Sequential search
    4. Unsuccessful searches for Ternary search

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

    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 for the ternary search (both successful and unsuccessful) in a table on a separate sheet and hand it in with this assignment.

    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. For example, for problem E2, indicate the appropriate rule or show the limit that lets you place one function above or below another in your list of functions. Also indicate which function grows fastest and which grows slowest.

    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:
      ~csci132/bin/submit csci132 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 10
    • The explanation and answers to the problems listed in part 2.
    • Turn in a discussion log.

    Home | | Syllabus | | Assignments | | Lecture Notes

    Constance Royden--croyden@mathcs.holycross.edu
    Computer Science 132--Data Structures
    Last Modified: March 27, 2014
    Page Expires: January 14, 2015