General Information
Progress Log
Week 0
Implemented various Union Find Algorithms on Image Grids
Found worst case examples for small instances
Week 1
Developed new Raster Scanning Algorithm for 4way connectivity.
Week 2
In Prague for TAMC 2010 Conference.
Week 3
Confirmed Correctness of 4way algorithm and extended to 8way
case.
Developed Model of Energy Balance Update Problem and explored
potential ccompetitive algorithms.
Week 4
New Potential Function generalizes to most scanning orders
without flattening.
Showed that no deterministic algorithm can be ccompetitive in
the list Energy Update problem.
Week 5
Showed that no randomized algoirthm can be ccompetitive in the
list Energy update Problem
Generalized to the Tree Energy Update Problem. Showed that MTR
is 3d2 competitive for a ddepth tree.
Last update: 7/2/2010
