Friday, November 16, 2018, 12:15-1pm (with pizza at noon)
ICSpace (POST 318B)
ICS Colloquium series:
Algorithms: Theory Meets Practice
Princeton University and Intertrust Technologies
Theory has an important role to play in computing practice. The faster speeds and larger memory sizes of current computers vastly increase the size of the design space of possible solutions for even simple problems. A theoretical approach to algorithm design helps to systematically explore this space. Such an approach can produce algorithms that are correct and efficient as well as simple to program. I shall illustrate these points with one or two real-life examples.
Robert Tarjan is James S. McDonnell Distinguished University Professor of Computer Science at Princeton University, and the Chief Scientist at Intertrust Technologies Corporation. He is an ACM Fellow and a recipient of the Turing award (jointly with John Hopcroft) for “fundamental achievements in the design and analysis of algorithms and data structures”.
He is the discoverer of several graph algorithms and together with Hopcroft was one of the first to advocate the adjacency-list representation for sparse graphs and to recognize the algorithmic importance of the depth-first search. In the ICS 311 Algorithms course we teach two of the algorithms that he discovered: strongly connected components using DFS and linear time selection of the k-th smallest element in an unsorted array. He was the first to prove the tight bound for the Union-Find data structure for disjoint sets that is used in Kruskal’s Minimum Spanning Tree algorithm. In graduate Algorithms and Data Structures courses we also teach Splay Tree and Fibonacci Heap data structures that he invented.