T-106.290 Ohjelmoinnin laboratoriotyöt

Subject: Array search (2 cr)

The purpose of this assignment is to study the performance of search algorithms on sorted arrays. The algorithms to be studied are:

• Linear scan over the array
• Binary search
• Interpolation search
• Fibonaccian search

Investigate the following issues:

• Size of the array (from a few entries to millions of entries)
• Distribution of the keys in the array (even vs. lumpy distributions)
• If none of the algorithms is always the best, suggest and benchmark a combination of these algorithms.

Investigate also at least two of the following issues:

• Effect of key type to the results, i.e. integer/floating point number/character strings of varying length.
• By default all your search routines should be implemented without recursion, but investigate how much recursion would slow them down.
• Run your tests in three significantly different machines.

Some references

• Aho, Hopcroft, Ullman, Data Structures and Algorithms
• Aho, Hopcorft, Ullman, The Design and Analysis of Computer Algorithms
• Cormen, Leiserson, Rivest:  Introduction to algorithms
• Horowitz, Sahni:  Fundamentals of Data Structures in Pascal
• Kingston, Algorithms and Data Structures
• Knuth: The Art of Computer Programming, volume 3 / Sorting and Searching
• Sedgewick:  Algorithms / Algorithms in C / Algorithms in C++
• Weiss:  Data Structures and Algorithm Analysis (various versions for Pascal, C, C++ and Java)
• Wirth, Algorithms + Data Structures = Programs