Algorithm Engineering - Michael T. Goodrich

. .

Résumé :
Alles ?ber die Implementation von Datenstrukturen und Algorithmen: Die Autoren zeigen Ihnen, dass Sie mehr ben?tigen als nur theoretisch-algorithmische Kenntnisse, n?mlich auch ingenieurtechnische Entwurfsprinzipien: abstrakte Datentypen, objektorientierte Entwurfsmuster und Strategien, die Robustheit und Benutzerfreundlichkeit sichern. Behandelt werden u.a. die schnelle Fourier-Transformation (FFT), Kryptologie, Parallelit?t und NP-Vollst?ndigkeit....

Biographie:

Michael T. Goodrich is a mathematician and computer scientist. He is a Chancellor's Professor and the chair of Department of Computer Science, of Donald Bren School of Information and Computer Sciences, a school of University of California, Irvine. Roberto Tamassia is the author of Algorithm Design: Foundations, Analysis, and Internet Examples, published by Wiley....

Sommaire:

I Fundamental Tools 1

1 Algorithm Analysis 3

1.1 Methodologies for Analyzing Algorithms? 5

1.2 Asymptotic Notation 13

1.3 A Quick Mathematical Review? 21

1.4 Case Studies in Algorithm Analysis? 31

1.5 Amortization? 34

1.6 Experimentation? 42

1.7 Exercises? 47

2 Basic Data Structures 55

2.1 Stack sand Queues? 57

2.2 Vectors, Lists, and Sequences? 65

2.3 Trees? 75

2.4 Priority Queues and Heaps? 94

2.5 Dictionaries and Hash Tables? 114

2.6 Java Example: Heap? 128

2.7 Exercises? 131

3 Search Trees and Skip Lists 139

3.1 Ordered Dictionaries and Binary Search Trees? 141

3.2 AVL Trees? 152

3.3 Bounded-Depth Search Trees? 159

3.4 Splay Trees? 185

3.5 Sk i p Lists? 195

3.6 Java Example: AVL and Red-Black Trees? 202

3.7 Exercises? 212

4 Sorting, Sets, and Selection 217

4.1 Merge-Sort? 219

4.2 The Set Abstract Data Type? 225

4.3 Quick -Sort? 235

4.4 A Lower Bound on Comparison-Based Sorting? 239

4.5 Buck et-Sort and Radix-Sort? 241

4.6 Comparison of Sorting Algorithms? 244

4.7 Selection? 245

4.8 Java Example: In-Place Quick -Sort? 248

4.9 Exercises? 251

5 Fundamental Techniques 257

5.1 The GreedyMethod? 259

5.2 Divide-and-Conquer? 263

5.3 Dynamic Programming? 274

5.4 Exercises? 282

II Graph Algorithms 285

6 Graphs 287

6.1 The Graph Abstract Data Type? 289

6.2 Data Structures for Graphs? 296

6.3 Graph Traversal? 303

6.4 Directed Graphs? 316

6.5 Java Example: Depth-First Search? 329

6.6 Exercises? 335

7 Weighted Graphs 339

7.1 Single-Source Shortest Paths? 341

7.2 All-Pairs Shortest Paths? 354

7.3 Minimum Spanning Trees? 360

7.4 Java Example: Dijk stra's Algorithm? 373

7.5 Exercises? 376

8 Network Flow and Matching 381

8.1 Flows and Cuts? 383

8.2 Maximum Flow? 387

8.3 Maximum BipartiteMatching? 396

8.4 Minimum-Cost Flow? 398

8.5 Java Example: Minimum-Cost Flow? 405

8.6 Exercises? 412

III Internet Algorithmics 415

9 Text Processing 417

9.1 Strings and PatternMatching Algorithms? 419

9.2 Tries? 429

9.3 Text Compression? 440

9.4 Text Similarity Testing? 443

9.5 Exercises? 447

10 Number Theory and Cryptography 451

10.1 Fundamental Algorithms Involving Numbers? 453

10.2 Cryptographic Computations? 471

10.3 Information Security Algorithms and Protocols? 481

10.4 The Fast Fourier Transform? 488

10.5 Java Example: FFT? 500

10.6 Exercises? 508

11 Network Algorithms 511

11.1 ComplexityMeasures and Models? 513

11.2 Fundamental Distributed Algorithms? 517

11.3 Broadcast and Unicast Routing? 530

11.4 Multicast Routing? 535

11.5 Exercises? 541

IV Additional Topics 545

12 Computational Geometry 547

12.1 Range Trees? 549

12.2 Priority Search Trees? 556

12.3 Quadtrees and k-D Trees? 561

12.4 The Plane Sweep Technique? 565

12.5 Convex Hulls? 572

12.6 Java Example: Convex Hull? 583

12.7 Exercises? 587

13 NP-Completeness 591

13.1 P and NP? 593

13.2 NP-Completeness? 599

13.3 Important NP-Complete Problems? 603

13.4 Approximation Algorithms? 618

13.5 Back track i ng and Branch-and-Bound? 627

13.6 Exercises? 638

14 Algorithmic Frameworks 643

14.1 External-Memory Alg...