Dan Larkin will present his research seminar/general exam on Tuesday April 30 at 2PM in Room 402. The members of his committee are: Bob Tarjan (advisor), Bob Sedgewick, and Moses Charikar. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----- Original Message ----- TITLE Experimental Heaps: a Comparative Study of Priority Queues ABSTRACT In many areas the theory-practice gap is neglected. One such divide which has widened in the past decade is that pertaining to priority queue variants. Most implementations in use today are based on classical binary heaps and some slight variations thereof, with a few libraries implementing binomial queues or other quick-melding structures developed in the 1980s. These choices are accompanied by experimentally backed claims that more complicated, and better-in-theory structures simply run slower on real-world workloads. This hasn't seemed to deter the theory community though, as a flurry of results has been published recently establishing new structures which achieve optimal theoretical bounds while claiming in some way to be better than older variants. Whether this claimed improvement is in theoretical elegance, implementational efficiency, or pedagogical convenience, the claims have not been thoroughly tested. Furthermore, previously published experimental work is outdated or suffers from a limited scope. This work seeks to reopen the discussion on narrowing the gap. Implementing both some classic structures and several new, untested variants, we collect a variety of performance metrics across several types of workloads. We include both relatively realistic workloads and purely contrived randomized workloads, which can nevertheless help shed light on practical properties of different structures. We also show that one such contrived workload, a very natural operation sequence found in a benchmark suite, is fundamentally degenerate. We identify trends which may help provide guidance to future practitioners and theoreticians alike. READING LIST Textbook: "Introduction to Algorithms," 2nd ed., T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Structures implemented: "Algorithm 232 heapsort," J. W. J. Williams. "A data structure for manipulating priority queues," J. Vuillemin. "Fibonacci heaps and their uses in improved network optimization algorithms," M. L. Fredman, R. E. Tarjan. "The pairing heap: A new form of self-adjusting heap," M. L. Fredman, R. Sedgewick, D. D. Sleator, R. E. Tarjan. "The weak-heap family of priority queues in theory and praxis," S. Edelkamp, A. Elmasry, J. Katajainen. "The violation heap: A relaxed Fibonacci-like heap," A. Elmasry. "Quake heaps: a simple alternative to Fibonacci heaps," T. M. Chan. "Rank-pairing heaps," B. Haeupler, S. Sen, R. E. Tarjan. "Strict fibonacci heaps," G. S. Brodal, G. Lagogiannis, R. E. Tarjan. Some previous experimental studies on heaps: "Pairing heaps: experiments and analysis," J. T. Stasko, J. S. Vitter. "The influence of caches on the performance of heaps," A. LaMarca, R. E. Ladner. "Fast priority queues for cached memory," P. Sanders.