The Algorithm Design Manual

Huge savings for students

Each student receives a 50% discount off of most books in the HSG Book Store. During class, please ask the instructor about purchase details.
List Price: $74.99
Price: $37.50
You Save: $37.50
5

{*DRAFT*}

Introduction to Algorithm Design

Algorithm Analysis

Data Structures

Sorting and Searching

Divide and Conquer

Randomized Algorithms and Hashing

Graph Traversal

Weighted Graph Algorithms

Combinatorial Search and Heuristic Methods

Dynamic Programming

NP-Completeness

Dealing with Hard Problems

How to Design Algorithms

14 A Catalog of Algorithmic Problems 437

15 Data Structures 439

15.1 Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440

15.2 Priority Queues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445

15.3 Sux Trees and Arrays . . . . . . . . . . . . . . . . . . . . . . . 448

15.4 Graph Data Structures . . . . . . . . . . . . . . . . . . . . . . . . 452

15.5 Set Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . 456

15.6 Kd-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460

16 Numerical Problems 465

16.1 Solving Linear Equations . . . . . . . . . . . . . . . . . . . . . . 467

16.2 Bandwidth Reduction . . . . . . . . . . . . . . . . . . . . . . . . 470

16.3 Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . . . 472

16.4 Determinants and Permanents . . . . . . . . . . . . . . . . . . . 475

16.5 Constrained/Unconstrained Optimization . . . . . . . . . . . . . 478

16.6 Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . . 482

16.7 Random Number Generation . . . . . . . . . . . . . . . . . . . . 486

16.8 Factoring and Primality Testing . . . . . . . . . . . . . . . . . . . 490

16.9 Arbitrary-Precision Arithmetic . . . . . . . . . . . . . . . . . . . 493

16.10Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 497

16.11Discrete Fourier Transform . . . . . . . . . . . . . . . . . . . . . 501

17 Combinatorial Problems 505

17.1 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506

17.2 Searching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510

17.3 Median and Selection . . . . . . . . . . . . . . . . . . . . . . . . . 514

17.4 Generating Permutations . . . . . . . . . . . . . . . . . . . . . . 517

17.5 Generating Subsets . . . . . . . . . . . . . . . . . . . . . . . . . . 521

17.6 Generating Partitions . . . . . . . . . . . . . . . . . . . . . . . . 524

17.7 Generating Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 528

17.8 Calendrical Calculations . . . . . . . . . . . . . . . . . . . . . . . 532

17.9 Job Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534

17.10Satisability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537

18 Graph Problems: Polynomial-Time 541

18.1 Connected Components . . . . . . . . . . . . . . . . . . . . . . . 542

18.2 Topological Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . 546

18.3 Minimum Spanning Tree . . . . . . . . . . . . . . . . . . . . . . . 549

18.4 Shortest Path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554

18.5 Transitive Closure and Reduction . . . . . . . . . . . . . . . . . . 559

18.6 Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562

18.7 Eulerian Cycle/Chinese Postman . . . . . . . . . . . . . . . . . . 565

18.8 Edge and Vertex Connectivity . . . . . . . . . . . . . . . . . . . . 568

16 CONTENTS

18.9 Network Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571

18.10Drawing Graphs Nicely . . . . . . . . . . . . . . . . . . . . . . . 574

18.11Drawing Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578

18.12Planarity Detection and Embedding . . . . . . . . . . . . . . . . 581

19 Graph Problems: NP-Har

Springer