Tampere University of Technology

TUTCRIS Research Portal

Improvements to Online Learning Algorithms with Applications to Binary Search Trees

Research output: Collection of articlesDoctoral Thesis

Details

Original languageEnglish
PublisherTampere University of Technology
Number of pages69
ISBN (Electronic)978-952-15-2176-8
ISBN (Print)978-952-15-2019-8
StatePublished - 24 Sep 2008
Publication typeG5 Doctoral dissertation (article)

Publication series

NameTampere University of Technology. Publication
PublisherTampere University of Technology
Volume748
ISSN (Print)1459-2045

Abstract

In this work we are motivated by the question: "How to automatically adapt to, or learn, structure in the past inputs of an algorithm?". This question might arise from the need to decrease the amount of consumed resources, such as run-time or money. In addition, we also consider, in part, the growing significance of the IO-issues in computation. A major focus is on studying data structures, such as binary search trees (BSTs). They are a common and practical solution to the problem of representing data such as sets; hence it is important to understand their properties. For the most part we work with algorithms which continuously serve requests under uncertainty about future inputs. These algorithms are called online algorithms. To analyze their performance we use the competitive analysis. In it the uncertainty over future inputs is not necessarily modeled stochastically, but rather we deal with the uncertainty by comparing our own performance to how well we could have done had we known the input sequence.

Open access publication

Country of publishing