CS 269S, Winter 2014: Theory Seminar
Bren Hall, Room 1423, 1pm
February 28, 2014:

Blame Trees

Pawel Pszona

Presenting a paper by Erik D. Demaine, Pavel Panchekha, David Wilson, Edward Z. Yang

A "blame query" in a version control system associates each line of a text file with the person that was the last to modify it. I will present "blame trees", data structures that allow for efficient merging of two versions of the same document with conflicting edits. The "blame tree" representation allows merging two documents in time proportional to the sum of logarithms of the sizes of shared regions, plus the cost of conflict resolution.