Essential Algorithms: A Practical Approach to Computer Algorithms

bindex.indd 05:47:54:PM 07/10/2013 Page 602

ffi rs.indd 05:53:16:PM 07/10/2013 Page i

Essential Algorithms

A Practical Approach to Computer

Algorithms

Rod Stephens

ffi rs.indd 05:53:16:PM 07/10/2013 Page ii

Essential Algorithms: A Practical Approach to Computer Algorithms

Published by

John Wiley & Sons, Inc.

10475 Crosspoint Boulevard

Indianapolis, IN 46256

www.wiley.com

Copyright © 2013 by John Wiley & Sons, Inc., Indianapolis, Indiana

Published simultaneously in Canada

ISBN: 978-1-118-61210-1

ISBN: 978-1-118-61276-7 (ebk)

ISBN: 978-1-118-79729-7 (ebk)

Manufactured in the United States of America

10 9 8 7 6 5 4 3 2 1

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or

by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted

under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permis￾sion of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright

Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 646-8600. Requests to the

Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111

River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.

com/go/permissions.

Limit of Liability/Disclaimer of Warranty: The publisher and the author make no representations or war￾ranties with respect to the accuracy or completeness of the contents of this work and specifi cally disclaim all

warranties, including without limitation warranties of fi tness for a particular purpose. No warranty may be

created or extended by sales or promotional materials. The advice and strategies contained herein may not

be suitable for every situation. This work is sold with the understanding that the publisher is not engaged in

rendering legal, accounting, or other professional services. If professional assistance is required, the services

of a competent professional person should be sought. Neither the publisher nor the author shall be liable for

damages arising herefrom. The fact that an organization or Web site is referred to in this work as a citation

and/or a potential source of further information does not mean that the author or the publisher endorses

the information the organization or website may provide or recommendations it may make. Further, readers

should be aware that Internet websites listed in this work may have changed or disappeared between when

this work was written and when it is read.

For general information on our other products and services please contact our Customer Care Department

within the United States at (877) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Wiley publishes in a variety of print and electronic formats and by print-on-demand. Some material included

with standard print versions of this book may not be included in e-books or in print-on-demand. If this book

refers to media such as a CD or DVD that is not included in the version you purchased, you may download

this material at http://booksupport.wiley.com. For more information about Wiley products,

visit www.wiley.com.

Library of Congress Control Number: 2013941603

Trademarks: Wiley and the Wiley logo are trademarks or registered trademarks of John Wiley & Sons, Inc.

and/or its affi liates, in the United States and other countries, and may not be used without written permission.

All other trademarks are the property of their respective owners. John Wiley & Sons, Inc. is not associated

with any product or vendor mentioned in this book.

iii

ffi rs.indd 05:53:16:PM 07/10/2013 Page iii

Rod Stephens started out as a mathematician, but while studying at MIT, he

discovered how much fun algorithms are. He took every algorithms course MIT

offered and has been writing complex algorithms ever since.

During his career, Rod has worked on an eclectic assortment of applications

in such fi elds as telephone switching, billing, repair dispatching, tax process￾ing, wastewater treatment, concert ticket sales, cartography, and training for

professional football players.

Rod is a Microsoft Visual Basic Most Valuable Professional (MVP) and has

taught introductory programming at ITT Technical Institute. He has written

more than 2 dozen books that have been translated into languages from all over

the world. He has also written more than 250 magazine articles covering C#,

Visual Basic, Visual Basic for Applications, Delphi, and Java.

Rod’s popular VB Helper website (www.vb-helper.com) receives several mil￾lion hits per month and contains tips, tricks, and example programs for Visual

Basic programmers. His C# Helper website (www.csharphelper.com) contains

similar material for C# programmers.

You can contact Rod at RodStephens@vb-helper.com or

RodStephens@csharphelper.com.

About the Author

iv

ffi rs.indd 05:53:16:PM 07/10/2013 Page iv

Executive Editor

Robert Elliott

Project Editor

Tom Dinse

Technical Editors

David Coleman

Jack Jianxiu Hao

George Kocur

Production Editor

Daniel Scribner

Copy Editor

Gayle Johnson

Editorial Manager

Mary Beth Wakefi eld

Freelancer Editorial Manager

Rosemarie Graham

Associate Director of Marketing

David Mayhew

Marketing Manager

Ashley Zurcher

Business Manager

Amy Knies

Production Manager

Tim Tate

Vice President and Executive

Group Publisher

Richard Swadley

Vice President and Executive

Publisher

Neil Edde

Associate Publisher

Jim Minatel

Project Coordinator, Cover

Katie Crocker

Proofreader

Josh Chase, Word One

Indexer

Robert Swanson

Cover Designer

Ryan Sneed

Credits

v

ffi rs.indd 05:53:16:PM 07/10/2013 Page v

Acknowledgments

Thanks to Bob Elliott, Tom Dinse, Gayle Johnson, and Daniel Scribner for all

of their hard work in making this book possible. Thanks also to technical edi￾tors George Kocur, Dave Colman, and Jack Jianxiu Hao for helping ensure the

information in this book is as accurate as possible. (Any remaining mistakes

are mine not theirs.)

vi

ffi rs.indd 05:53:16:PM 07/10/2013 Page vi

Introduction xv

Chapter 1 Algorithm Basics 1

Chapter 2 Numerical Algorithms 25

Chapter 3 Linked Lists 55

Chapter 4 Arrays 83

Chapter 5 Stacks and Queues 111

Chapter 6 Sorting 131

Chapter 7 Searching 163

Chapter 8 Hash Tables 169

Chapter 9 Recursion 185

Chapter 10 Trees 227

Chapter 11 Balanced Trees 277

Chapter 12 Decision Trees 297

Chapter 13 Basic Network Algorithms 325

Chapter 14 More Network Algorithms 355

Chapter 15 String Algorithms 377

Chapter 16 Cryptography 397

Chapter 17 Complexity Theory 419

Chapter 18 Distributed Algorithms 435

Chapter 19 Interview Puzzles 465

Appendix A Summary of Algorithmic Concepts 477

Appendix B Solutions to Exercises 487

Glossary 559

Index 573

Contents at a Glance

vii

ftoc.indd 05:53:41:PM 07/10/2013 Page vii

Introduction xv

Chapter 1 Algorithm Basics 1

Approach 2

Algorithms and Data Structures 3

Pseudocode 3

Algorithm Features 6

Big O Notation 7

Common Runtime Functions 11

Visualizing Functions 17

Practical Considerations 17

Summary 19

Exercises 20

Chapter 2 Numerical Algorithms 25

Randomizing Data 25

Generating Random Values 25

Randomizing Arrays 31

Generating Nonuniform Distributions 33

Finding Greatest Common Divisors 33

Performing Exponentiation 35

Working with Prime Numbers 36

Finding Prime Factors 37

Finding Primes 39

Testing for Primality 40

Performing Numerical Integration 42

The Rectangle Rule 42

The Trapezoid Rule 43

Contents

viii Contents

ftoc.indd 05:53:41:PM 07/10/2013 Page viii

Adaptive Quadrature 44

Monte Carlo Integration 48

Finding Zeros 49

Summary 51

Exercises 52

Chapter 3 Linked Lists 55

Basic Concepts 55

Singly Linked Lists 56

Iterating Over the List 57

Finding Cells 57

Using Sentinels 58

Adding Cells at the Beginning 59

Adding Cells at the End 60

Inserting Cells After Other Cells 61

Deleting Cells 62

Doubly Linked Lists 63

Sorted Linked Lists 65

Linked-List Algorithms 66

Copying Lists 67

Sorting with Insertionsort 68

Linked List Selectionsort 69

Multithreaded Linked Lists 70

Linked Lists with Loops 71

Marking Cells 72

Using Hash Tables 74

List Retracing 75

List Reversal 76

Tortoise and Hare 78

Loops in Doubly Linked Lists 80

Summary 81

Exercises 81

Chapter 4 Arrays 83

Basic Concepts 83

One-dimensional Arrays 86

Finding Items 86

Finding Minimum, Maximum, and Average 86

Inserting Items 88

Removing Items 89

Nonzero Lower Bounds 89

Two Dimensions 90

Higher Dimensions 91

Triangular Arrays 94

Sparse Arrays 97

Contents ix

ftoc.indd 05:53:41:PM 07/10/2013 Page ix

Find a Row or Column 100

Get a Value 101

Set a Value 101

Delete a Value 104

Matrices 105

Summary 108

Exercises 108

Chapter 5 Stacks and Queues 111

Stacks 111

Linked-List Stacks 112

Array Stacks 113

Double Stacks 115

Stack Algorithms 117

Queues 123

Linked-List Queues 123

Array Queues 124

Specialized Queues 127

Summary 128

Exercises 128

Chapter 6 Sorting 131

O(N2

) Algorithms 132

Insertionsort in Arrays 132

Selectionsort in Arrays 134

Bubblesort 135

O(N log N) Algorithms 138

Heapsort 139

Quicksort 145

Mergesort 153

Sub O(N log N) Algorithms 156

Countingsort 156

Bucketsort 157

Summary 159

Exercises 160

Chapter 7 Searching 163

Linear Search 164

Binary Search 165

Interpolation Search 166

Summary 167

Exercises 168

Chapter 8 Hash Tables 169

Hash Table Fundamentals 170

Chaining 171

x Contents

ftoc.indd 05:53:41:PM 07/10/2013 Page x

Open Addressing 172

Removing Items 174

Liner Probing 174

Quadratic Probing 176

Pseudorandom Probing 178

Double Hashing 178

Ordered Hashing 179

Summary 181

Exercises 182

Chapter 9 Recursion 185

Basic Algorithms 186

Factorial 186

Fibonacci Numbers 188

Tower of Hanoi 189

Graphical Algorithms 193

Koch Curves 193

Hilbert Curve 196

Sierpin´ ski Curve 197

Gaskets 200

Backtracking Algorithms 201

Eight Queens Problem 203

Knight’s Tour 206

Selections and Permutations 209

Selections with Loops 210

Selections with Duplicates 211

Selections Without Duplicates 213

Permutations with Duplicates 214

Permutations Without Duplicates 215

Recursion Removal 216

Tail Recursion Removal 216

Storing Intermediate Values 218

General Recursion Removal 220

Summary 222

Exercises 223

Chapter 10 Trees 227

Tree Terminology 227

Binary Tree Properties 231

Tree Representations 234

Building Trees in General 234

Building Complete Trees 236

Tree Traversal 237

Preorder Traversal 238

Inorder Traversal 240

Postorder Traversal 242

Contents xi

ftoc.indd 05:53:41:PM 07/10/2013 Page xi

Depth-fi rst Traversal 243

Traversal Run Times 244

Sorted Trees 245

Adding Nodes 245

Finding Nodes 247

Deleting Nodes 248

Threaded Trees 250

Building Threaded Trees 251

Using Threaded Trees 254

Specialized Tree Algorithms 256

The Animal Game 256

Expression Evaluation 258

Quadtrees 260

Tries 266

Summary 270

Exercises 271

Chapter 11 Balanced Trees 277

AVL Trees 278

Adding Values 278

Deleting Values 281

2-3 Trees 282

Adding Values 283

Deleting Values 284

B-Trees 287

Adding Values 288

Deleting Values 289

Balanced Tree Variations 291

Top-down B-trees 291

B+trees 291

Summary 293

Exercises 293

Chapter 12 Decision Trees 297

Searching Game Trees 298

Minimax 298

Initial Moves and Responses 302

Game Tree Heuristics 303

Searching General Decision Trees 305

Optimization Problems 306

Exhaustive Search 307

Branch and Bound 309

Decision Tree Heuristics 310

Other Decision Tree Problems 316

Summary 322

Exercises 322

xii Contents

ftoc.indd 05:53:41:PM 07/10/2013 Page xii

Chapter 13 Basic Network Algorithms 325

Network Terminology 325

Network Representations 328

Traversals 331

Depth-fi rst Traversal 331

Breadth-fi rst Traversal 334

Connectivity Testing 335

Spanning Trees 337

Minimal Spanning Trees 338

Finding Paths 339

Finding Any Path 339

Label-Setting Shortest Paths 340

Label-Correcting Shortest Paths 344

All-Pairs Shortest Paths 345

Summary 350

Exercises 351

Chapter 14 More Network Algorithms 355

Topological Sorting 355

Cycle Detection 359

Map Coloring 359

Two-coloring 360

Three-coloring 362

Four-coloring 362

Five-coloring 363

Other Map-coloring Algorithms 367

Maximal Flow 368

Work Assignment 370

Minimal Flow Cut 372

Summary 374

Exercises 375

Chapter 15 String Algorithms 377

Matching Parentheses 378

Evaluating Arithmetic Expressions 379

Building Parse Trees 380

Pattern Matching 381

DFAs 381

Building DFAs for Regular Expressions 383

NFAs 386

String Searching 387

Calculating Edit Distance 391

Summary 394

Exercises 394

Chapter 16 Cryptography 397

Terminology 398

Transposition Ciphers 399

Contents xiii

ftoc.indd 05:53:41:PM 07/10/2013 Page xiii

Row/column Transposition 399

Column Transposition 401

Route Ciphers 403

Substitution Ciphers 404

Caesar Substitution 404

Vigenère Cipher 405

Simple Substitution 407

One-Time Pads 408

Block Ciphers 408

Substitution-Permutation Networks 409

Feistel Ciphers 410

Public-Key Encryption and RSA 412

Euler’s Totient Function 413

Multiplicative Inverses 413

An RSA Example 414

Practical Considerations 414

Other Uses for Cryptography 415

Summary 416

Exercises 417

Chapter 17 Complexity Theory 419

Notation 420

Complexity Classes 421

Reductions 424

3SAT 425

Bipartite Matching 426

NP-Hardness 426

Detection, Reporting, and Optimization Problems 427

Detection ≤

p Reporting 427

Reporting ≤

p Optimization 428

Reporting ≤

p

Detection 428

Optimization ≤

p Reporting 429

NP-Complete Problems 429

Summary 431

Exercises 432

Chapter 18 Distributed Algorithms 435

Types of Parallelism 436

Systolic Arrays 436

Distributed Computing 438

Multi-CPU Processing 440

Race Conditions 440

Deadlock 444

Quantum Computing 445

Distributed Algorithms 446

Debugging Distributed Algorithms 446

Embarrassingly Parallel Algorithms 447

Mergesort 449