Essential Algorithms : a Practical Approach to Computer Algorithms

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
Sierpinski 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