2010-03-15 Poughkeepsie ACM Speaker Jon Bentley

Reposted here from Poughkeepsie Chapter of the ACM web site.

Poughkeepsie Chapter of the Association For Computing Machinery

            aaa         ccccccc      mmmmm   mmmmm
          a   a       cc     cc     mm mm   mm mm
        aa   aa      cc      c     mm  mm mm  mm
      aaaaaaaaa     cc            mm   mmm   mm
     aa     aa     cc      c     mm    m    mm   MEETING NOTICE
    aa     aa     cc     cc     mm         mm
   aa     aa      cccccccc     mm         mm

Program: Quicksort 2010: Implementing and Analyzing a Family of Functions

Speaker: Jon Bentley, Avaya Labs Research

About the Topic:

For half a century, the fastest comparison-based sort functions have been variants of Hoare’s classic Quicksort. But exactly which variants are best on today’s machines? This talk describes experiments to search for the fastest possible implementation of Quicksort; our hunt is a celebration of the Joy of Programming. We were surprised by the results: some old champions are now painfully slow, while long-discarded variants have become lightning fast. Along the way, we discovered a desperate need for a new cost model for sorting, and we laid the foundation for the Dual-Pivot Quicksort we wrote for Java Development Kit 7. We found that explicitly considering a large family (or product line) of algorithms is a powerful approach. (This talk describes joint work with Vladimir Yaroslavskiy and Joshua Bloch.)

About the Speaker:

Jon Bentley is a computer scientist at Avaya Labs Research. His interests include programming techniques, algorithm design, and the design of software tools and interfaces. He has written three books on programming and articles on a variety of topics, ranging from the theory of algorithms to software engineering.

Possibly his best known work is the book “Programming Pearls” (see www.cs.bell-labs.com/cm/cs/pearls/) which is based on the columns he wrote in the 1980's for the Communications of the ACM.

Bentley received a B.S. at Stanford in 1974 and an M.S. and Ph.D. from the University of North Carolina in 1976; he then taught Computer Science at Carnegie Mellon for six years. He joined Bell Labs in 1982, and retired in 2001 to join Avaya Labs.

Jon has hiked the Catskill 3500 peaks nine times (including once solo in the winter), the 46 4000-foot peaks in the Adirondacks, the 48 4000-footers in New Hampshire's Whites, and the five 4000-footers in Vermont's Green Mountains. He has made numerous rock climbing ascents, both frontcountry and backcountry, on at least two continents. He has numerous Medical Technician rankings, many of them relating to Wilderness EMT.

When: 7:30 pm, Monday, Mar 15, 2010

Where: Donnelly Hall, Room 225.
Marist College, Route 9, Poughkeepsie, NY
(Donnelly Hall is Building 6 on the Marist campus map at www.marist.edu/about/map.html.)

Parking: It will be spring break at Marist, so parking will be easy.

Cost: Free and open to the public

Dinner: 6 pm, Palace Diner, 194 Washington Street, POK, 845.473.1576
Menu: www.thepalacediner.com/menu_pg.htm

All are welcome to join us for dinner. (Go north on the Route 9 Arterial to the St. Francis Hospital exit, turn right, turn right again. The Palace is one block further along on the right.)

We thank Marist College for hosting the chapter's meetings.

Refreshments are served after the meeting. For further information, email collier@acm.org or call 845.522.1971.

Site Map. This page is available on the web at http://pok.acm.org.