Title: Sorting and Searching Strings

Description

Any database that stores strings needs a data structure to handle searching and sorting. Fast and efficient algorithms for this purpose are discussed and analyzed in the paper "Fast Algorithms for Sorting and Searching Strings," which was published in the Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1997, by Jon Bentley and Robert Sedgewick. It has been approved by Professor Arvo, and I have provided him with a copy.

This paper compares the efficiency of binary trees, digital tries, and ternary trees in sorting and searching strings. It also includes several sorting algorithms in C for ternary trees. I plan to implement binary trees and ternary trees in LISP and then to compare their time complexities for searching and sorting, both theoretically and practically. I find the mathematical derivations of complexity and the proofs of the theorems in the paper to be challenging and interesting. The topics of search trees and computational complexity have been covered in CS20.

Major Milestones

1. Get approval of the paper "Fast Algorithms for Sorting and Searching Strings." (completed)
2. Read the paper thoroughly.
3. Understand and prove the theorems presented in the paper.
4. Understand the algorithms provided in the paper.
5. Derive the computational complexities for those algorithms.
6. Implement binary tree and ternary tree algorithms in LISP. Also consider how to implement them in C or Java.
7. Summarize my findings in a final report.
8. Present my report to the class.

Participants

 Back to main page