Lehigh University - CSE: Bentley

Dr. Jon Bentley

"Binary Trees, Quicksort and Me"

Thursday, February 10, 4:30 PM

Packard Lab, Room 101

Abstract: Binary trees and Quicksort were both invented in the early 1960's; I first learned about them in 1970. This talk starts by reviewing the basics, and then presents a novel analysis of run time. I've used trees in many programs, and I've built a widely used system sort function. The talk next describes how to engineer these structures to solve real problems. The talk concludes by sketching how, as a researcher, I've been privileged to extend the simple ideas to solve problems in strings and computational geometry. In short, this talk describes my two old friends, binary trees and Quicksort, and the joy they have given me over a few decades.

Bio: 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 -- including the engaging and insightful 'Programming Pearls' -- and articles on topics ranging from the theory of algorithms to software engineering. He received a B.S. from Stanford in 1974 and an M.S. and Ph.D. from the University of North Carolina in 1976, then taught Computer Science at Carnegie Mellon for six years. He joined Bell Labs in 1982, and retired in 2001 to join Avaya Labs. He has been a visiting faculty member at West Point and Princeton, and has been a member of teams that have shipped software tools, telephone switches, telephones and web services.

Dr. Bentley will be visiting much of the day. To speak with him, contact Henry Baird (hsb2@lehigh.edu).

		Dr. Jon Bentley "Binary Trees, Quicksort and Me" Thursday, February 10, 4:30 PM Packard Lab, Room 101 Abstract: Binary trees and Quicksort were both invented in the early 1960's; I first learned about them in 1970. This talk starts by reviewing the basics, and then presents a novel analysis of run time. I've used trees in many programs, and I've built a widely used system sort function. The talk next describes how to engineer these structures to solve real problems. The talk concludes by sketching how, as a researcher, I've been privileged to extend the simple ideas to solve problems in strings and computational geometry. In short, this talk describes my two old friends, binary trees and Quicksort, and the joy they have given me over a few decades. Bio: 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 -- including the engaging and insightful 'Programming Pearls' -- and articles on topics ranging from the theory of algorithms to software engineering. He received a B.S. from Stanford in 1974 and an M.S. and Ph.D. from the University of North Carolina in 1976, then taught Computer Science at Carnegie Mellon for six years. He joined Bell Labs in 1982, and retired in 2001 to join Avaya Labs. He has been a visiting faculty member at West Point and Princeton, and has been a member of teams that have shipped software tools, telephone switches, telephones and web services. Dr. Bentley will be visiting much of the day. To speak with him, contact Henry Baird (hsb2@lehigh.edu).