Algorithms and data structures
Subtitle: the basic toolbox
By: Kurt Mehlhorn, Peter Sanders.
Contributors: Sanders, Peter, 1967-
Publisher: Springer
Published: 2008
Place of publication: Berlin
Language: eng
Format: Hardcover
Number of pages: 300
ISBN-13: 9783540779773; 9783540779780
Subjects: Data structures (Computer science); Computer algorithms
Notes: Includes bibliographical references (p. [273]-283) and index.
Table of contents: label: 1
title: Appetizer: Integer Arithmetics
pagenum: 1; label: 1.1
title: Addition
pagenum: 2; label: 1.2
title: Multiplication: The School Method
pagenum: 3; label: 1.3
title: Result Checking
pagenum: 6; label: 1.4
title: A Recursive version of the School Method
pagenum: 7; label: 1.5
title: Karatsuba Multiplication
pagenum: 9; label: 1.6
title: Algorithm Engineering
pagenum: 11; label: 1.7
title: The Programs
pagenum: 13; label: 1.8
title: Proofs of Lemma 1.5 and Theorem 1.7
pagenum: 16; label: 1.9
title: Implementation Notes; label: 1.10
title: Historical Notes and Further Findings
pagenum: 18; label: 2
title: Introduction
pagenum: 19; label: 2.1
title: Asymptotic Notation
pagenum: 19; label: 2.2
title: The Machine Model
pagenum: 20; label: 2.3
title: Pseudocode
pagenum: 23; label: 2.4
title: Designing Correct Algorithms and Programs
pagenum: 31; label: 2.5
title: An Example - Binary Search
pagenum: 34; label: 2.6
title: Basic Algorithm Analysis
pagenum: 41; label: 2.7
title: Average-Case Analysis
pagenum: 36; label: 2.8
title: Randomized Algorithms
pagenum: 45; label: 2.9
title: Graphs
pagenum: 49; label: 2.10
title: P and NP
pagenum: 49; label: 2.11
title: Implementation Notes
pagenum: 56; label: 2.12
title: Historical Notes and Further Findings
pagenum: 57; label: 3
title: Representing Sequences by Arrays and Linked Lists
pagenum: 59; label: 3.1
title: Linked Lists
pagenum: 60; label: 3.2
title: Unbounded Arrays
pagenum: 66; label: 3.3
title: *Amortized Analysis
pagenum: 71; label: 3.4
title: Stacks and Queues
pagenum: 74; label: 3.5
title: Lists Versus Arrays
pagenum: 77; label: 3.6
title: Implementation Notes
pagenum: 78; label: 3.7
title: Historical Notes and Further Findings
pagenum: 79; label: 4
title: Hash Tables and Associative Arrays
pagenum: 81; label: 4.1
title: Hashing and Chaining
pagenum: 83; label: 4.2
title: Universal Hashing
pagenum: 85; label: 4.3
title: Hashing with Linear Probing
pagenum: 90; label: 4.4
title: Chaining Versus Linear Probing
pagenum: 92; label: 4.5
title: *Perfect Hashing
pagenum: 92; label: 4.6
title: Implementation Notes
pagenum: 95; label: 4.7
title: Historical Notes and Further Findings
pagenum: 97; label: 5
title: Sorting and Selection
pagenum: 99; label: 5.1
title: Simple Sorters
pagenum: 101; label: 5.2
title: Mergesort - an O(n log n) Sorting Algorithm
pagenum: 103; label: 5.3
title: A Lower Bound
pagenum: 106; label: 5.4
title: Quicksort
pagenum: 108; label: 5.5
title: Selection
pagenum: 114; label: 5.6
title: Breaking the Lower Bound
pagenum: 116; label: 5.7
title: *External Sorting
pagenum: 118; label: 5.8
title: Implementation Notes
pagenum: 122; label: 5.9
title: Historical Notes and Further Findings
pagenum: 124; label: 6
title: Priority Queues
pagenum: 127; label: 6.1
title: Binary Heaps
pagenum: 129; label: 6.2
title: Addressable Priority Queues
pagenum: 133; label: 6.3
title: *External Memory
pagenum: 139; label: 6.4
title: Implementation Notes
pagenum: 141; label: 6.5
title: Historical Notes and Further Findings
pagenum: 142; label: 7
title: Sorted Sequences
pagenum: 145; label: 7.1
title: Binary Search Trees
pagenum: 147; label: 7.2
title: (a, b)-Trees and Red-Black Trees
pagenum: 149; label: 7.3
title: More Operations
pagenum: 156; label: 7.4
title: Amortized Analysis of Update Operations
pagenum: 158; label: 7.5
title: Augmented Search Trees
pagenum: 160; label: 7.6
title: Implementation Notes
pagenum: 162; label: 7.7
title: Historical Notes and Further Findings
pagenum: 164; label: 8
title: Graph Representation
pagenum: 167; label: 8.1
title: Unordered Edge Sequences
pagenum: 168; label: 8.2
title: Adjacency Arrays - Static Graphs
pagenum: 168; label: 8.3
title: Adjacency Lists - Dynamic Graphs
pagenum: 170; label: 8.4
title: The Adjacency Matrix Representation
pagenum: 171; label: 8.5
title: Implicit Representations
pagenum: 172; label: 8.6
title: Implementation Notes
pagenum: 172; label: 8.7
title: Historical Notes and Further Findings
pagenum: 174; label: 9
title: Graph Traversal
pagenum: 175; label: 9.1
title: Breadth-First Search
pagenum: 176; label: 9.2
title: Depth-First Search
pagenum: 178; label: 9.3
title: Implementation Notes
pagenum: 188; label: 9.4
title: Historical Notes and Further Findings
pagenum: 189; label: 10
title: Shortest Paths
pagenum: 191; label: 10.1
title: From Basic Concepts to a Generic Algorithm
pagenum: 192; label: 10.2
title: Directed Acyclic Graphs
pagenum: 195; label: 10.3
title: Nonnegative Edge Costs (Dijkstra's Algorithm)
pagenum: 196; label: 10.4
title: *Average-Case Analysis of Dijkstra's Algorithm
pagenum: 199; label: 10.5
title: Monotone Integer Priority Queues
pagenum: 201; label: 10.6
title: Arbitrary Edge Costs (Bellman-Ford Algorithm)
pagenum: 206; label: 10.7
title: All-Pairs Shortest Paths and Node Potentials
pagenum: 207; label: 10.8
title: Shortest-Path Queries
pagenum: 209; label: 10.9
title: Implementation Notes
pagenum: 213; label: 10.10
title: Historical Notes and Further Findings
pagenum: 214; label: 11
title: Minimum Spanning Trees
pagenum: 217; label: 11.1
title: Cut and Cycle Properties
pagenum: 218; label: 11.2
title: The Jarnik-Prim Algorithm
pagenum: 219; label: 11.3
title: Kruskal's Algorithm
pagenum: 221; label: 11.4
title: The Union-Find Data Structure
pagenum: 222; label: 11.5
title: *External Memory
pagenum: 225; label: 11.6
title: Applications
pagenum: 228; label: 11.7
title: Implementation Notes
pagenum: 231; label: 11.8
title: Historical Notes and Further Findings
pagenum: 231; label: 12
title: Generic Approaches to Optimization
pagenum: 233; label: 12.1
title: Linear Programming - a Black-Box Solver
pagenum: 234; label: 12.2
title: Greedy Algorithms - Never Look Back
pagenum: 239; label: 12.3
title: Dynamic Programming - Building It Piece by Piece
pagenum: 243; label: 12.4
title: Systematic Search - When in Doubt, Use Brute Force
pagenum: 246; label: 12.5
title: Local Search - Think Globally, Act Locally
pagenum: 249; label: 12.6
title: Evolutionary Algorithms
pagenum: 259; label: 12.7
title: Implementation Notes
pagenum: 261; label: 12.8
title: Historical Notes and Further Findings
pagenum: 262; label: A
title: Appendix
pagenum: 263; label: A.1
title: Mathematical Symbols
pagenum: 263; label: A.2
title: Mathematical Concepts
pagenum: 264; label: A.3
title: Basic Probability Theory
pagenum: 266; label: A.4
title: Useful Formulae
pagenum: 269; title: References
pagenum: 273; title: Index
pagenum: 285