CSCI 132 Data Structures--Spring 2014

    Home | | Syllabus | | Assignments | | Lecture Notes

    Assignment 7 Solutions

    Part 1:

    Solution to ternary() function

    Comparison trees

    Below is the comparison tree for the ternary function as described in the assignment:

    Table of number of comparisons

    The number of comparisons made depends on how you implemented your code. In general the numbers should be similar to the ones given below. If your numbers are much higher than the ones given below then your search algorithm is doing more comparisons than necessary. 

    Search compare results for ternary function:

List length:     5       10      20      100      1000
Successful    4.40     5.70    7.42    12.12     18.38
Unsuccessful  6.72     8.34   10.66    15.66     22.04

    Part 2:
    Solutions to problems on asymptotic analysis.

    Problem 1 (E2): Ordering of functions.

    Problem 2 (E15):

    Home | | Syllabus | | Assignments | | Lecture Notes