E-Book Content
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
Foreword Buy me not [25].
iii
iv
Mehlhorn, Sanders June 11, 2005
v
Contents 1 Amuse Geule: Integer Arithmetics 1.1 Addition . . . . . . . . . . . . . . . . . . . 1.2 Multiplication: The School Method . . . . 1.3 A Recursive Version of the School Method . 1.4 Karatsuba Multiplication . . . . . . . . . . 1.5 Implementation Notes . . . . . . . . . . . . 1.6 Further Findings . . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
3 4 4 6 8 10 11
2 Introduction 2.1 Asymptotic Notation . . . . . . . . . . . . . . . . . 2.2 Machine Model . . . . . . . . . . . . . . . . . . . . 2.3 Pseudocode . . . . . . . . . . . . . . . . . . . . . . 2.4 Designing Correct Programs . . . . . . . . . . . . . 2.5 Basic Program Analysis . . . . . . . . . . . . . . . . 2.6 Average Case Analysis and Randomized Algorithms 2.7 Data Structures for Sets and Sequences . . . . . . . . 2.8 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 Implementation Notes . . . . . . . . . . . . . . . . . 2.10 Further Findings . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
13 14 16 19 23 25 29 32 32 37 38