Dynamic Maintenance of Alphabetic Search Trees
Project Description
Alphabetic trees are binary search trees in which data are kept in the leaves
While there is a huge literature on maintaining optimal cost trees when data is kept in internal nodes, not that much is known when data are kept in the leaves.
While there is a huge literature on maintaining optimal cost trees when data is kept in internal nodes, not that much is known when data are kept in the leaves.
Supervisor
GOLIN Mordecai Jay
Quota
2
Course type
UROP1000
UROP1100
UROP2100
UROP3100
UROP4100
Applicant's Roles
In this project students will (i) experiment with algorithms for efficiently maintaining the optimality of alphabet trees under insertion and deletion of data and (ii) mathematically analyze the performance of these algorithms.
Applicant's Learning Objectives
leaning how to experiment with and exactly analyze algorithms.
Complexity of the project
Moderate