Robert E. Tarjan, winner of the Association for Computing Machinery's A.M. Turing Award, discusses his work to understand the performance of the "union-find" data structure, which he showed in 1975 to have an almost constant time per operation over long enough sequences. This gives a time which was proportional to inverse Ackermann's function of the number of operations and elements. This clip is taken from an interview conducted with Tarjan by Roy Levin for the ACM on July 12, 2017. Video of the full interview is available as part of Tarjan’s ACM profile at amturing.acm.o....
12 окт 2020
