General Information

Name: Jarett Schwartz (jdschwar[@]princeton.edu)
Home University: Princeton University
Mentor: Robert E. Tarjan, Princeton University
Project: Linear time Union-Find for Image Processing
Office: CoRE 634

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 4-way connectivity.
Week 2
In Prague for TAMC 2010 Conference.
Week 3
Confirmed Correctness of 4-way algorithm and extended to 8-way case.
Developed Model of Energy Balance Update Problem and explored potential c-competitive algorithms.
Week 4
New Potential Function generalizes to most scanning orders without flattening.
Showed that no deterministic algorithm can be c-competitive in the list Energy Update problem.
Week 5
Showed that no randomized algoirthm can be c-competitive in the list Energy update Problem
Generalized to the Tree Energy Update Problem. Showed that MTR is 3d-2 competitive for a d-depth tree.

Last update: 7/2/2010
HTML Hit Counter