Essential Algorithms A Practical Approach to Computer Algorithms

by Stephens, Rod

• ISBN13: 9781118612101
• ISBN10: 1118612108
• Format: Paperback
• Copyright: 2013-08-12
• Publisher: Wiley

Summary

A friendly and accessible introduction to the most useful algorithms

Computer algorithms are the basic recipes for programming. Professional programmers need to know how to use algorithms to solve difficult programming problems. Written in simple, intuitive English, this book describes how and when to use the most practical classic algorithms, and even how to create new algorithms to meet future needs. The book also includes a collection of questions that can help readers prepare for a programming job interview.

• Reveals methods for manipulating common data structures such as arrays, linked lists, trees, and networks
• Addresses advanced data structures such as heaps, 2-3 trees, B-trees
• Addresses general problem-solving techniques such as branch and bound, divide and conquer, recursion, backtracking, heuristics, and more
• Reviews sorting and searching, network algorithms, and numerical algorithms
• Includes general problem-solving techniques such as brute force and exhaustive search, divide and conquer, backtracking, recursion, branch and bound, and more

In addition, Essential Algorithms features a companion website that includes full instructor materials to support training or higher ed adoptions.

Author Biography

Rod Stephens began his career as a mathematician, but while at MIT he was lured into the intriguing world of algorithms and has been programming ever since. An award-winning instructor, he regularly addresses conferences and has written 26 books that have been translated into nearly a dozen languages.

Table of Contents

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

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

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

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

Depth-first 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

Chapter 13 Basic Network Algorithms 325

Network Terminology 325

Network Representations 328

Traversals 331

Depth-first Traversal 331

Breadth-first 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

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

Dining Philosophers 449

The Two Generals Problem 452

Byzantine Generals 453

Consensus 455

Leader Election 458

Snapshot 459

Clock Synchronization 460

Summary 462

Exercises 462

Chapter 19 Interview Puzzles 465

Asking Interview Puzzle Questions 467

Answering Interview Puzzle Questions 468

Summary 472

Exercises 474

Appendix A Summary of Algorithmic Concepts 477

Appendix B Solutions to Exercises 487

Glossary 559

Index 573