SCS Undergraduate Thesis Topics

2005-2006
Student Advisor(s) Thesis Topic
Kanat Tangwonsan Guy Blelloch Active Data Structures and Applications to Dynamic and Kinetic Algorithms

Dynamic alogorithms are a class of algorithms proven particularly challenging to design, analyze and implement. These algorithms maintain the input and output relationship as the input undergoes changes. Unfortunately, most known techniques for designing and implementing such algorithms are very complex, as suggested by the minuscule number of successful implementations. Self-Adjusting Computation, a recent development that combines algorithmic and programming-languages techniques, has helped simplify the task of algorithms engineering for dynamic algorithms and create new possibilities in kinetic algorithms. To this end, I conjecture that problem in many domains can be solved more efficiently if the self-adjusting framework is supplemented with external data structures that perform orthogonally to the core system.

As my thesis, I propose to investigate a class of data structures, akin to the retroactive data structures [Demaine '04], and incorporate it to the existing framework. This incorporation is expected to create new frontiers in efficient algorithm dynamization. Concrete examples include: dynamic/kinetic 3D convex hull and dynamic shortest-path.


Close this window