Algorithms and Data Structures

by Mehlhorn, Kurt; Sanders, Peter

• ISBN13: 9783540779773
• ISBN10: 3540779779
• Format: Hardcover
• Copyright: 2008-09-30
• Publisher: Springer-Nature New York Inc

Summary

Algorithms are at the heart of every nontrivial computer application, and algorithmics is a modern and active area of computer science. Every computer scientist and every professional programmer should know about the basic algorithmic toolbox: structures that allow efficient organization and retrieval of data, frequently used algorithms, and basic techniques for modeling, understanding and solving algorithmic problems.

Author Biography

Prof. Kurt Mehlhorn was appointed a Fellow of the ACM (1999) "for important contributions in complexity theory and in the design, analysis, and practice of combinatorial and geometric algorithms." A Professor of Computer Science at Saarland University since 1975, and a director of the Max-Planck-Institut f++r Informatik in Saarbr++cken, he has coauthored over 250 refereed papers/articles, in collaboration with 200 researchers. Other awards include the Leibniz Award of the German Research Foundation in 1986 and the Konrad Zuse Medal of the German Society for Informatics in 1995.Prof. Peter Sanders is a Professor of Computer Science at the University of Karlsruhe. A leading researcher in the area of theoretical and experimental algorithm analysis, in particular related to efficient algorithms for parallel processing and communication in networks, his responsibilities include organizing the European Symposium on Algorithms in Karlsruhe in 2008.The authors have considerable experience teaching on the topic of algorithms and working on related industrial projects.

Table of Contents

Appetizer: Integer Arithmetics	p. 1
Addition	p. 2
Multiplication: The School Method	p. 3
Result Checking	p. 6
A Recursive Version of the School Method	p. 7
Karatsuba Multiplication	p. 9
Algorithm Engineering	p. 11
The Programs	p. 13
Proofs of Lemma 1.5 and Theorem 1.7	p. 16
Implementation Notes	p. 17
Historical Notes and Further Findings	p. 18
Introduction	p. 19
Asymptotic Notation	p. 20
The Machine Model	p. 23
Pseudocode	p. 26
Designing Correct Algorithms and Programs	p. 31
An Example - Binary Search	p. 34
Basic Algorithm Analysis	p. 36
Average-Case Analysis	p. 41
Randomized Algorithms	p. 45
Graphs	p. 49
P and NP	p. 53
Implementation Notes	p. 56
Historical Notes and Further Findings	p. 57
Representing Sequences by Arrays and Linked Lists	p. 59
Linked Lists	p. 60
Unbounded Arrays	p. 66
*Amortized Analysis	p. 71
Stacks and Queues	p. 74
Lists Versus Arrays	p. 77
Implementation Notes	p. 78
Historical Notes and Further Findings	p. 79
Hash Tables and Associative Arrays	p. 81
Hashing with Chaining	p. 83
Universal Hashing	p. 85
Hashing with Linear Probing	p. 90
Chaining Versus Linear Probing	p. 92
*Perfect Hashing	p. 92
Implementation Notes	p. 95
Historical Notes and Further Findings	p. 97
Sorting and Selection	p. 99
Simple Sorters	p. 101
Mergesort - an O(n log n) Sorting Algorithm	p. 103
A Lower Bound	p. 106
Quicksort	p. 108
Selection	p. 114
Breaking the Lower Bound	p. 116
*External Sorting	p. 118
Implementation Notes	p. 122
Historical Notes and Further Findings	p. 124
Priority Queues	p. 127
Binary Heaps	p. 129
Addressable Priority Queues	p. 133
*External Memory	p. 139
Implementation Notes	p. 141
Historical Notes and Further Findings	p. 142
Sorted Sequences	p. 145
Binary Search Trees	p. 147
(a, b)-Trees and Red-Black Trees	p. 149
More Operations	p. 156
Amortized Analysis of Update Operations	p. 158
Augmented Search Trees	p. 160
Implementation Notes	p. 162
Historical Notes and Further Findings	p. 164
Graph Representation	p. 167
Unordered Edge Sequences	p. 168
Adjacency Arrays - Static Graphs	p. 168
Adjacency Lists-Dynamic Graphs	p. 170
The Adjacency Matrix Representation	p. 171
Implicit Representations	p. 172
Implementation Notes	p. 172
Historical Notes and Further Findings	p. 174
Graph Traversal	p. 175
Breadth-First Search	p. 176
Depth-First Search	p. 178
Implementation Notes	p. 188
Historical Notes and Further Findings	p. 189
Shortest Paths	p. 191
From Basic Concepts to a Generic Algorithm	p. 192
Directed Acyclic Graphs	p. 195
Nonnegative Edge Costs (Dijkstra's Algorithm)	p. 196
*Average-Case Analysis of Dijkstra's Algorithm	p. 199
Monotone Integer Priority Queues	p. 201
Arbitrary Edge Costs (Bellman-Ford Algorithm)	p. 206
All-Pairs Shortest Paths and Node Potentials	p. 207
Shortest-Path Queries	p. 209
Implementation Notes	p. 213
Historical Notes and Further Findings	p. 214
Minimum Spanning Trees	p. 217
Cut and Cycle Properties	p. 218
The Jarník-R-im Algorithm	p. 219
Kruskal's Algorithm	p. 221
The Union-Find Data Structure	p. 222
*External Memory	p. 225
Applications	p. 228
Implementation Notes	p. 231
Historical Notes and Further Findings	p. 231
Generic Approaches to Optimization	p. 233
Linear Programming - a Black-Box Solver	p. 234
Greedy Algorithms - Never Look Back	p. 239
Dynamic Programming - Building It Piece by Piece	p. 243
Systematic Search - When in Doubt, Use Brute Force	p. 246
Local Search - Think Globally, Act Locally	p. 249
Evolutionary Algorithms	p. 259
Implementation Notes	p. 261
Historical Notes and Further Findings	p. 262
Appendix	p. 263
MathematicalSymbols	p. 263
Mathematical Concepts	p. 264
Basic Probability Theory	p. 266
UsefulFormulae	p. 269
References	p. 273
Index	p. 285
Table of Contents provided by Publisher. All Rights Reserved.