+612 9045 4394

CHECKOUT

Algorithm Design

Foundations, Analysis, and Internet Examples

Paperback Published: 15th October 2001
ISBN: 9780471383659
Number Of Pages: 720

Paperback

\$290.49
Ships in 10 to 15 business days

Earn 581 Qantas Points
on this Book

<p> Are you looking for something different in your Algorithms text? Are you looking for an Algorithms text that offers theoretical analysis techniques as well as design patterns and experimental methods for the engineering of algorithms? Michael Goodrich and Roberto Tamassia, authors of the successful, Data Structures and Algorithms in Java, 2/e, have written Algorithm Design, a text designed to provide a comprehensive introduction to the design, implementation and analysis of computer algorithms and data structures from a modern perspective.</p> <p> Written for an undergraduate, junior-senior algorithms course this text offers several implementation case studies and uses Internet applications to motivate many topics such as hashing, sorting and searching. </p>

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

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 AlgorithmsÂ  645

14.2 Parallel AlgorithmsÂ  657

14.3 Online AlgorithmsÂ  667

14.4 ExercisesÂ  680

A Useful Mathematical Facts 685

Bibliography 689

Index 698

ISBN: 9780471383659
ISBN-10: 0471383651
Audience: Tertiary; University or College
Format: Paperback
Language: English
Number Of Pages: 720
Published: 15th October 2001
Country of Publication: US
Dimensions (cm): 23.35 x 19.1  x 2.63
Weight (kg): 1.07
Edition Number: 1

Earn 581 Qantas Points
on this Book