Binary Search Trees and the Dynamic Optimality Conjecture

• Grant number: 24/04708-2
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: August 01, 2024
• End date: July 31, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Cristina Gomes Fernandes
• Grantee: Bruno Armond Braga
• Host Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil

Abstract

This project has as its main objective the study and research of the mathematical delimitations of the cost of operations in binary search trees and also the exploration of different binary search trees that are asymptotically efficient. As part of this study, the student will implement the structures and algorithms studied and prepare a didactic text presenting some of the topics studied in the project.