Title: An Efficient Algorithm for Computing Ulam Distance
Speaker: Tim Naumovitz, Rutgers University
Date: Wednesday, September 16, 2015 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The question of computing ulam distance arises out of a hope of attacking the difficult related problem of computing (or approximating) edit distance. In this talk, I'll introduce the notion of ulam distance and show how the task of computing ulam distance can be reduced to a discrete nearest neighbor problem. Subsequently, I'll show how one can use techniques motivated by binary search to solve this problem. If there's time, I might lift up the proverbial rug at the end of the talk and look at the things I swept under it.