An edition of Algorithms and data structures (2008)

Algorithms and data structures

the basic toolbox

by

  • 1 Want to read
Cover of: Algorithms and data structures by Kurt Mehlhorn, Kurt Mehlhorn
Read Listen

My Reading Lists:

Create a new list

Check-In

×Close
Add an optional check-in date. Check-in dates are used to track yearly reading goals.
Today
Notes
  • 1 Want to read
Notes

Download Options

Check nearby libraries

Buy this book

Last edited by ImportBot
October 4, 2021 | History
Edit
An edition of Algorithms and data structures (2008)

Algorithms and data structures

the basic toolbox

by

  • 1 Want to read

The design and analysis of basic algorithms that should be part of every programmer's toolkit.

Publish Date
Publisher
Springer
Language
English
Pages
300

Check nearby libraries

Buy this book

Previews available in: English

Subjects

Computer algorithms, Data structures (Computer science), algorithms, data structures, graphs, hash tables, sorting, Data structures (computer science)
Edition Availability
Cover of: Algorithms and data structures
Algorithms and data structures: the basic toolbox
2008, Springer
Hardcover in English

Add another edition?

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.

Published in
Berlin

Classifications

Library of Congress
QA76.9.D35 M47 2008, QA75.5-76.95

The Physical Object

Format
Hardcover
Pagination
xii, 300 p. :
Number of pages
300

Edition Identifiers

Open Library
OL21897978M
Internet Archive
algorithmsdatast00mehl_045
ISBN 13
9783540779773, 9783540779780
LCCN
2008926816
OCLC/WorldCat
221217367
Library Thing
7819176
Goodreads
3222432

Work Identifiers

Work ID
OL6777805W

Source records

Library of Congress MARC record
Library 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)

No community reviews have been submitted for this work.

Lists

See All

History

Download catalog record: RDF / JSON
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