Algorithms and Data Structures - The Basic Toolbox.pdf

文档介绍：Entwurf-Entwurf-Entwurf-Entwurf-Entwurf-Entwurf-Entwurf-Entwurf
Concise Algorithmics
or
Algorithms and Data Structures —
The Basic Toolbox
or. . .
Kurt Mehlhorn and Peter Sanders
Entwurf-Entwurf-Entwurf-Entwurf-Entwurf-Entwurf-Entwurf-Entwurf
Mehlhorn, Sanders June 11, 2005 iii
Foreword
Buy me not [25].
iv Mehlhorn, Sanders June 11, 2005 v
Contents
1 Amuse Geule: Integer Arithmetics 3
Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Multiplication: The School Method . . . . . . . . . . . . . . . . . . 4
A Recursive Version of the School Method . . . . . . . . . . . . . . . 6
Karatsuba Multiplication . . . . . . . . . . . . . . . . . . . . . . . . 8
Implementation Notes . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Further Findings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Introduction 13
Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Machine Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
Pseudocode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Designing Correct Programs . . . . . . . . . . . . . . . . . . . . . . 23
Basic Program Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 25
Average Case Analysis and Randomized Algorithms . . . . . . . . . 29
Data Structures for Sets and Sequences . . . . . . . . . . . . . . . . . 32
Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Implementation Notes . . . . . . . . . . . . . . . . . . . . . . . . . . 37
Further Findings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3 Representing Sequences by Arrays and Linked Lists 39
Unbounded Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Linked Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Stacks and Queues . . . . . . . . . . . .