MISC

2009年

Finding nearest larger neighbors A case study in algorithm design and analysis

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
  • Tetsuo Asano
  • ,
  • Sergey Bereg
  • ,
  • David Kirkpatrick

5760
開始ページ
249
終了ページ
260
記述言語
英語
掲載種別
DOI
10.1007/978-3-642-03456-5_17

Designing and analysing efficient algorithms is important in practical applications, but it is also fun and frequently instructive, even for simple problems with no immediate applications. In this self-contained paper we try to convey some of fun of algorithm design and analysis. Hopefully, the reader will find the discussion instructive as well. We focus our attention on a single problem that we call the All Nearest Larger Neighbors Problem. Part of the fun in designing algorithms for this problem is the rich variety of algorithms that arise under slightly different optimization criteria. We also illustrate several important analytic techniques, including amortization, and correctness arguments using non-trivial loop invariants. We hope, in this modest way, to reflect our deep admiration for the many contributions of Kurt Mehlhorn to the theory, practice and appreciation of algorithm design and analysis. © 2009 Springer Berlin Heidelberg.

リンク情報
DOI
https://doi.org/10.1007/978-3-642-03456-5_17
URL
https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=70349881792&origin=inward
ID情報
  • DOI : 10.1007/978-3-642-03456-5_17
  • ISSN : 0302-9743
  • ISSN : 1611-3349
  • SCOPUS ID : 70349881792

エクスポート
BibTeX RIS