Textbook

# Algorithm Design: Foundations, Analysis, and Internet Examples

ISBN: 978-0-471-38365-9
720 pages
For Instructors

## Description

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.

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.

See More

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

See More

• Algorithmic design patterns are presented to provide a clear approach for implementation algorithms.
• Internet Algorithms. Are you interested in improving student interest in the study of algorithms? Algorithms Design encourages the learning of traditional algorithm topics now finding new applications in the Internet, as well as topics of specific interest to companies and research labs working on Internet applications.
• Authors Goodrich and Tamassia replace complex average-case analysis of sophisticated data structures with intuitive analysis of simple data structures and algorithms. Use of randomization will allow instructors to avoid the need for motivating complex analyses with assumptions about input distributions.
• Strong website support offers algorithm animations. Tutorials provide intuition and increased understanding of algorithms.
• Data structures, code examples provide concrete examples of Java implementations.
• Do your students respond to visual learning tools? Goodrich and Tamassia make use of visual proofs to help students better understand algebraic and induction proofs.
See More

## Related Websites / Extra

See More
Instructors Resources
Wiley Instructor Companion Site
Website

Website includes many aides for both students and instructors, including:

• On-line transparencies
• Solutions
• Special hint server
• Problems database
• Java source code that offers specific examples of several algorithm engineering techniques and topics.
See More
See Less
Students Resources
Wiley Student Companion Site
Website

Website includes many aides for both students and instructors, including:

• On-line transparencies
• Solutions
• Special hint server
• Problems database
• Java source code that offers specific examples of several algorithm engineering techniques and topics.
See More
See Less