Public defence in Information and Computer Science, M.Sc. Wanchote Jiamjitrak

Opponent: Assistant Professor László Kozma, Freie Universität Berlin, Germany
Custos: Assistant Professor Parinya Chalermsook, Aalto University School of Science, Department of Computer Science

The thesis is publicly displayed 10 days before the defence in the publication archive Aaltodoc of Aalto University.

Electronic thesis

Public defence announcement: 

Imagine you have a row of boxes with numbers inside, sorted from smallest to largest. You need to find a specific number in one of the boxes while opening as few boxes as possible. One way to do this is by opening each box one by one, but this might take a long time. A smarter way is to use "binary search". You start by opening the box in the middle. If the number you are looking for is smaller than the number in the box, then you know the number must be in the left half. If it is larger, then you know it's in the right half. You keep repeating this process until you find the right box. This method is faster because it takes advantage of the sorted order of the numbers. Binary search can be represented by a tree-like structure called a "binary search tree (BST)". The long-standing conjecture states that there is the best BST algorithm such that it is as good as every other algorithm. In this thesis, we explore ways to find the most efficient BST using two methods: potential functions and extremal combinatorics, which results in unifying, strengthening, and deriving new bounds for BSTs.

Contact details of the doctoral student: [email protected]