Coding job interviews often require problem-solving with algorithms. Providing an easy-to-read introduction to computer algorithms, Essential Algorithms describes a number of important classical algorithms and explains when each is appropriate. The book defines how to analyze algorithms to understand their behavior. Most importantly, it teaches techniques that the reader can use to create new algorithms to meet future needs. Featuring exercises and solutions, this accessible text helps programmers and students prepare for programming job interviews that typically include algorithmic questions. Methods can be applied to any programming language.
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