<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'>Dan Larkin will present his research seminar/general exam on Tuesday April 30 at <br>2PM in Room 402.  The members of his committee are:  Bob Tarjan (advisor), Bob <br>Sedgewick, and Moses Charikar.  Everyone is invited to attend his talk, and those <br>faculty wishing to remain for the oral exam following are welcome to do so.  His <br>abstract and reading list follow below.<br><br><hr id="zwchr"><div style="color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><div dir="ltr"><div style=""><span style="font-family:arial,sans-serif;font-size:13px">TITLE</span></div><div style=""><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div><div style=""><span style="font-family:arial,sans-serif;font-size:13px">Experimental Heaps: a Comparative Study of Priority Queues</span></div>
<span style="font-family:arial,sans-serif;font-size:13px"><div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></div>ABSTRACT</span><div><font face="arial, sans-serif"><br></font><div style="font-family:arial,sans-serif;font-size:13px">
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.</div>
<div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px">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.</div>
<div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px"><span class="">READING</span> <span class="">LIST</span></div><div style="font-family:arial,sans-serif;font-size:13px">
<br></div><div style="font-family:arial,sans-serif;font-size:13px">Textbook:</div><div style="font-family:arial,sans-serif;font-size:13px">"Introduction to Algorithms," 2nd ed., T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein.</div>
<div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px">Structures implemented:</div><div style="font-family:arial,sans-serif;font-size:13px">"Algorithm 232 heapsort," J. W. J. Williams.</div>
<div style="font-family:arial,sans-serif;font-size:13px">"A data structure for manipulating priority queues," J. Vuillemin.</div><div style="font-family:arial,sans-serif;font-size:13px">"Fibonacci heaps and their uses in improved network optimization algorithms," M. L. Fredman, R. E. Tarjan.</div>
<div style="font-family:arial,sans-serif;font-size:13px">"The pairing heap: A new form of self-adjusting heap," M. L. Fredman, R. Sedgewick, D. D. Sleator, R. E. Tarjan.</div><div style="font-size:13px;font-family:arial,sans-serif">
"The weak-heap family of priority queues in theory and praxis," S. Edelkamp, A. Elmasry, J. Katajainen.</div><div style="font-family:arial,sans-serif;font-size:13px">"The violation heap: A relaxed Fibonacci-like heap," A. Elmasry.</div>
<div style="font-family:arial,sans-serif;font-size:13px">"Quake heaps: a simple alternative to Fibonacci heaps," T. M. Chan.<br></div><div style="font-size:13px;font-family:arial,sans-serif">"Rank-pairing heaps," B. Haeupler, S. Sen, R. E. Tarjan.</div>
<div style="font-family:arial,sans-serif;font-size:13px">"Strict fibonacci heaps," G. S. Brodal, G. Lagogiannis, R. E. Tarjan.<br></div><div style="font-family:arial,sans-serif;font-size:13px"><br></div><div style="font-family:arial,sans-serif;font-size:13px">
Some previous experimental studies on heaps:</div><div style="font-family:arial,sans-serif;font-size:13px">"Pairing heaps: experiments and analysis," J. T. Stasko, J. S. Vitter.</div><div style="font-family:arial,sans-serif;font-size:13px">
"The influence of caches on the performance of heaps," A. LaMarca, R. E. Ladner.</div><div style="font-family:arial,sans-serif;font-size:13px">"Fast priority queues for cached memory," P. Sanders.</div>
</div></div><div class="gmail_extra"><br></div></div><br></div></body></html>