An edition of Algorithms and data structures
(2008)
Algorithms and data structures
the basic toolbox
by Kurt Mehlhorn
- 0 Ratings
- 1 Want to read
- 0 Currently reading
- 0 Have read
Share
×Close
The design and analysis of basic algorithms that should be part of every programmer's toolkit.
Check nearby libraries
Buy this book
Previews available in: English
Showing 1 featured edition. View all 1 editions?
| Edition | Availability |
|---|---|
1
Algorithms and data structures: the basic toolbox
2008, Springer
Hardcover
in English
3540779779 9783540779773
|
aaaa
Libraries near you:
WorldCat
|
Book Details
Table of Contents
1.
Appetizer: Integer Arithmetics
Page 1
1.1.
Addition
Page 2
1.2.
Multiplication: The School Method
Page 3
1.3.
Result Checking
Page 6
1.4.
A Recursive version of the School Method
Page 7
1.5.
Karatsuba Multiplication
Page 9
1.6.
Algorithm Engineering
Page 11
1.7.
The Programs
Page 13
1.8.
Proofs of Lemma 1.5 and Theorem 1.7
Page 16
1.9.
Implementation Notes
1.10.
Historical Notes and Further Findings
Page 18
2.
Introduction
Page 19
2.1.
Asymptotic Notation
Page 19
2.2.
The Machine Model
Page 20
2.3.
Pseudocode
Page 23
2.4.
Designing Correct Algorithms and Programs
Page 31
2.5.
An Example - Binary Search
Page 34
2.6.
Basic Algorithm Analysis
Page 41
2.7.
Average-Case Analysis
Page 36
2.8.
Randomized Algorithms
Page 45
2.9.
Graphs
Page 49
2.10.
P and NP
Page 49
2.11.
Implementation Notes
Page 56
2.12.
Historical Notes and Further Findings
Page 57
3.
Representing Sequences by Arrays and Linked Lists
Page 59
3.1.
Linked Lists
Page 60
3.2.
Unbounded Arrays
Page 66
3.3.
*Amortized Analysis
Page 71
3.4.
Stacks and Queues
Page 74
3.5.
Lists Versus Arrays
Page 77
3.6.
Implementation Notes
Page 78
3.7.
Historical Notes and Further Findings
Page 79
4.
Hash Tables and Associative Arrays
Page 81
4.1.
Hashing and Chaining
Page 83
4.2.
Universal Hashing
Page 85
4.3.
Hashing with Linear Probing
Page 90
4.4.
Chaining Versus Linear Probing
Page 92
4.5.
*Perfect Hashing
Page 92
4.6.
Implementation Notes
Page 95
4.7.
Historical Notes and Further Findings
Page 97
5.
Sorting and Selection
Page 99
5.1.
Simple Sorters
Page 101
5.2.
Mergesort - an O(n log n) Sorting Algorithm
Page 103
5.3.
A Lower Bound
Page 106
5.4.
Quicksort
Page 108
5.5.
Selection
Page 114
5.6.
Breaking the Lower Bound
Page 116
5.7.
*External Sorting
Page 118
5.8.
Implementation Notes
Page 122
5.9.
Historical Notes and Further Findings
Page 124
6.
Priority Queues
Page 127
6.1.
Binary Heaps
Page 129
6.2.
Addressable Priority Queues
Page 133
6.3.
*External Memory
Page 139
6.4.
Implementation Notes
Page 141
6.5.
Historical Notes and Further Findings
Page 142
7.
Sorted Sequences
Page 145
7.1.
Binary Search Trees
Page 147
7.2.
(a, b)-Trees and Red-Black Trees
Page 149
7.3.
More Operations
Page 156
7.4.
Amortized Analysis of Update Operations
Page 158
7.5.
Augmented Search Trees
Page 160
7.6.
Implementation Notes
Page 162
7.7.
Historical Notes and Further Findings
Page 164
8.
Graph Representation
Page 167
8.1.
Unordered Edge Sequences
Page 168
8.2.
Adjacency Arrays - Static Graphs
Page 168
8.3.
Adjacency Lists - Dynamic Graphs
Page 170
8.4.
The Adjacency Matrix Representation
Page 171
8.5.
Implicit Representations
Page 172
8.6.
Implementation Notes
Page 172
8.7.
Historical Notes and Further Findings
Page 174
9.
Graph Traversal
Page 175
9.1.
Breadth-First Search
Page 176
9.2.
Depth-First Search
Page 178
9.3.
Implementation Notes
Page 188
9.4.
Historical Notes and Further Findings
Page 189
10.
Shortest Paths
Page 191
10.1.
From Basic Concepts to a Generic Algorithm
Page 192
10.2.
Directed Acyclic Graphs
Page 195
10.3.
Nonnegative Edge Costs (Dijkstra's Algorithm)
Page 196
10.4.
*Average-Case Analysis of Dijkstra's Algorithm
Page 199
10.5.
Monotone Integer Priority Queues
Page 201
10.6.
Arbitrary Edge Costs (Bellman-Ford Algorithm)
Page 206
10.7.
All-Pairs Shortest Paths and Node Potentials
Page 207
10.8.
Shortest-Path Queries
Page 209
10.9.
Implementation Notes
Page 213
10.10.
Historical Notes and Further Findings
Page 214
11.
Minimum Spanning Trees
Page 217
11.1.
Cut and Cycle Properties
Page 218
11.2.
The Jarnik-Prim Algorithm
Page 219
11.3.
Kruskal's Algorithm
Page 221
11.4.
The Union-Find Data Structure
Page 222
11.5.
*External Memory
Page 225
11.6.
Applications
Page 228
11.7.
Implementation Notes
Page 231
11.8.
Historical Notes and Further Findings
Page 231
12.
Generic Approaches to Optimization
Page 233
12.1.
Linear Programming - a Black-Box Solver
Page 234
12.2.
Greedy Algorithms - Never Look Back
Page 239
12.3.
Dynamic Programming - Building It Piece by Piece
Page 243
12.4.
Systematic Search - When in Doubt, Use Brute Force
Page 246
12.5.
Local Search - Think Globally, Act Locally
Page 249
12.6.
Evolutionary Algorithms
Page 259
12.7.
Implementation Notes
Page 261
12.8.
Historical Notes and Further Findings
Page 262
A.
Appendix
Page 263
A.1.
Mathematical Symbols
Page 263
A.2.
Mathematical Concepts
Page 264
A.3.
Basic Probability Theory
Page 266
A.4.
Useful Formulae
Page 269
References
Page 273
Index
Page 285
Edition Notes
Includes bibliographical references (p. [273]-283) and index.
Classifications
The Physical Object
ID Numbers
Source records
Library of Congress MARC recordLibrary of Congress MARC record
Internet Archive item record
Internet Archive item record
Internet Archive item record
Internet Archive item record
Library of Congress MARC record
Better World Books record
Better World Books record
marc_nuls MARC record
Internet Archive item record
ISBNdb
Community Reviews (0)
Feedback?Lists
See All
| October 4, 2021 | Edited by ImportBot | import existing book |
| June 28, 2019 | Edited by MARC Bot | import existing book |
| December 4, 2010 | Edited by Open Library Bot | Added subjects from MARC records. |
| July 31, 2010 | Edited by 96.242.73.8 | added description |
| December 10, 2009 | Created by WorkBot | add works page |