T-106.290 Ohjelmoinnin laboratoriotyöt

Subject: Tree search (3 or 4 cr)

The purpose of this assignment is to study the performance of tree search algorithms, their search and update performance. The algorithms to be studied are:

• Unbalanced binary search trees
• AVL-trees or red-black trees
• 4-way digital trees
• Treaps (a randomized tree)
• Patricia tree
• Judy

Use integers as key types, but vary their number and distribution. The data is another integer, which you can use to check the search results. Measure also the amount of memory consumed.

In 4 credit version, you should additionally

• Use strings of varying length and distributions as keys
• Benchmark also iterating over the keys

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