# Essential Algorithms

## A Practical Approach to Computer Algorithms Using Python and C#

2. Edition July 2019

800 Pages, Softcover*Textbook*

**978-1-119-57599-3**

A friendly introduction to the most useful algorithms written in simple, intuitive English

The revised and updated second edition of Essential Algorithms, offers an accessible introduction to computer algorithms. The book contains a description of important classical algorithms and explains when each is appropriate. The author shows how to analyze algorithms in order to understand their behavior and teaches techniques that the can be used to create new algorithms to meet future needs. The text includes useful algorithms such as: methods for manipulating common data structures, advanced data structures, network algorithms, and numerical algorithms. It also offers a variety of general problem-solving techniques.

In addition to describing algorithms and approaches, the author offers details on how to analyze the performance of algorithms. The book is filled with exercises that can be used to explore ways to modify the algorithms in order to apply them to new situations. This updated edition of Essential Algorithms:

* Contains explanations of algorithms in simple terms, rather than complicated math

* Steps through powerful algorithms that can be used to solve difficult programming problems

* Helps prepare for programming job interviews that typically include algorithmic questions

* Offers methods can be applied to any programming language

* Includes exercises and solutions useful to both professionals and students

* Provides code examples updated and written in Python and C#

Essential Algorithms has been updated and revised and offers professionals and students a hands-on guide to analyzing algorithms as well as the techniques and applications. The book also includes a collection of questions that may appear in a job interview. The book's website will include reference implementations in Python and C# (which can be easily applied to Java and C++).

Chapter 1 Algorithm Basics 1

Approach 2

Algorithms and Data Structures 2

Pseudocode 3

Algorithm Features 6

Big O Notation 7

Rule 1 8

Rule 2 8

Rule 3 9

Rule 4 9

Rule 5 10

Common Run Time Functions 11

1 11

Log N 11

Sqrt N 14

N 14

N log N 15

N² 15

2^N 15

N! 16

Visualizing Functions 16

Practical Considerations 18

Summary 19

Exercises 20

Chapter 2 Numerical Algorithms 23

Randomizing Data 23

Generating Random Values 23

Generating Values 24

Ensuring Fairness 26

Getting Fairness from Biased Sources 28

Randomizing Arrays 29

Generating Nonuniform Distributions 30

Making Random Walks 31

Making Self-Avoiding Walks 33

Making Complete Self-Avoiding Walks 34

Finding Greatest Common Divisors 36

Calculating Greatest Common Divisors 36

Extending Greatest Common Divisors 38

Performing Exponentiation 40

Working with Prime Numbers 42

Finding Prime Factors 42

Finding Primes 44

Testing for Primality 45

Performing Numerical Integration 47

The Rectangle Rule 48

The Trapezoid Rule 49

Adaptive Quadrature 50

Monte Carlo Integration 54

Finding Zeros 55

Gaussian Elimination 57

Forward Elimination 58

Back Substitution 60

The Algorithm 61

Least Squares Fits 62

Linear Least Squares 62

Polynomial Least Squares 64

Summary 67

Exercises 68

Chapter 3 Linked Lists 71

Basic Concepts 71

Singly Linked Lists 72

Iterating Over the List 73

Finding Cells 73

Using Sentinels 74

Adding Cells at the Beginning 75

Adding Cells at the End 76

Inserting Cells After Other Cells 77

Deleting Cells 78

Doubly Linked Lists 79

Sorted Linked Lists 81

Self-Organizing Linked Lists 82

Move to Front (MTF) 83

Swap 83

Count 84

Hybrid Methods 84

Pseudocode 85

Linked-List Algorithms 86

Copying Lists 86

Sorting with Insertionsort 87

Sorting with Selectionsort 88

Multithreaded Linked Lists 90

Linked Lists with Loops 91

Marking Cells 92

Using Hash Tables 93

List Retracing 94

List Reversal 95

Tortoise and Hare 98

Loops in Doubly Linked Lists 100

Summary 100

Exercises 101

Chapter 4 Arrays 103

Basic Concepts 103

One-Dimensional Arrays 106

Finding Items 106

Finding Minimum, Maximum, and Average 107

Finding Median 108

Finding Mode 109

Inserting Items 112

Removing Items 113

Nonzero Lower Bounds 114

Two Dimensions 114

Higher Dimensions 115

Triangular Arrays 118

Sparse Arrays 121

Find a Row or Column 123

Get a Value 124

Set a Value 125

Delete a Value 127

Matrices 129

Summary 131

Exercises 132

Chapter 5 Stacks and Queues 135

Stacks 135

Linked-List Stacks 136

Array Stacks 138

Double Stacks 139

Stack Algorithms 141

Reversing an Array 141

Train Sorting 142

Tower of Hanoi 143

Stack Insertionsort 145

Stack Selectionsort 146

Queues 147

Linked-List Queues 148

Array Queues 148

Specialized Queues 151

Priority Queues 151

Deques 152

Binomial Heaps 152

Binomial Trees 152

Binomial Heaps 154

Merging Trees 155

Merging Heaps 156

Merging Tree Lists 156

Merging Trees 158

Enqueue 161

Dequeue 162

Runtime 163

Summary 163

Exercises 164

Chapter 6 Sorting 167

O(N² ) Algorithms 168

Insertionsort in Arrays 168

Selectionsort in Arrays 170

Bubblesort 171

O(NlogN) Algorithms 174

Heapsort 175

Storing Complete Binary Trees 175

Defining Heaps 176

Implementing Heapsort 180

Quicksort 181

Analyzing Quicksort's Run Time 182

Picking a Dividing Item 184

Implementing Quicksort with Stacks 185

Implementing Quicksort in Place 185

Using Quicksort 188

Mergesort 189

Sub O(NlogN) Algorithms 192

Countingsort 192

Pigeonhole Sort 193

Bucketsort 195

Summary 197

Exercises 198

Chapter 7 Searching 201

Linear Search 202

Binary Search 203

Interpolation Search 204

Majority Voting 205

Summary 207

Exercises 208

Chapter 8 Hash Tables 209

Hash Table Fundamentals 210

Chaining 211

Open Addressing 213

Removing Items 214

Linear Probing 215

Quadratic Probing 217

Pseudorandom Probing 219

Double Hashing 219

Ordered Hashing 219

Summary 222

Exercises 222

Chapter 9 Recursion 227

Basic Algorithms 228

Factorial 228

Fibonacci Numbers 230

Rod-Cutting 232

Brute Force 233

Recursion 233

Tower of Hanoi 235

Graphical Algorithms 238

Koch Curves 239

Hilbert Curve 241

SierpiDski Curve 243

Gaskets 246

The Skyline Problem 247

Lists 248

Divide and Conquer 249

Backtracking Algorithms 252

Eight Queens Problem 254

Knight's Tour 257

Selections and Permutations 260

Selections with Loops 261

Selections with Duplicates 262

Selections without Duplicates 264

Permutations with Duplicates 265

Permutations without Duplicates 266

Round-Robin Scheduling 267

Odd Number of Teams 268

Even Number of Teams 270

Implementation 271

Recursion Removal 273

Tail Recursion Removal 274

Dynamic Programming 275

Bottom-Up Programming 277

General Recursion Removal 277

Summary 280

Exercises 281

Chapter 10 Trees 285

Tree Terminology 285

Binary Tree Properties 289

Tree Representations 292

Building Trees in General 292

Building Complete Trees 295

Tree Traversal 296

Preorder Traversal 297

Inorder Traversal 299

Postorder Traversal 300

Breadth-First Traversal 301

Traversal Uses 302

Traversal Run Times 303

Sorted Trees 303

Adding Nodes 303

Finding Nodes 306

Deleting Nodes 306

Lowest Common Ancestors 309

Sorted Trees 309

Parent Pointers 310

Parents and Depths 311

General Trees 312

Euler Tours 314

All Pairs 316

Threaded Trees 317

Building Threaded Trees 318

Using Threaded Trees 320

Specialized Tree Algorithms 322

The Animal Game 322

Expression Evaluation 324

Interval Trees 326

Building the Tree 328

Intersecting with Points 329

Intersecting with Intervals 330

Quadtrees 332

Adding Items 335

Finding Items 336

Tries 337

Adding Items 339

Finding Items 341

Summary 342

Exercises 342

Chapter 11 Balanced Trees 349

AVL Trees 350

Adding Values 350

Deleting Values 353

2-3 Trees 354

Adding Values 355

Deleting Values 356

B-Trees 359

Adding Values 360

Deleting Values 361

Balanced Tree Variations 362

Top-down B-trees 363

B+trees 363

Summary 365

Exercises 365

Chapter 12 Decision Trees 367

Searching Game Trees 368

Minimax 369

Initial Moves and Responses 373

Game Tree Heuristics 374

Searching General Decision Trees 375

Optimization Problems 376

Exhaustive Search 377

Branch and Bound 379

Decision Tree Heuristics 381

Random Search 381

Improving Paths 382

Simulated Annealing 384

Hill Climbing 385

Sorted Hill Climbing 386

Other Decision Tree Problems 387

Generalized Partition Problem 387

Subset Sum 388

Bin Packing 388

Cutting Stock 389

Knapsack 390

Traveling Salesman Problem 391

Satisfiability 391

Swarm Intelligence 392

Ant Colony Optimization 393

General Optimization 393

Traveling Salesman 393

Bees Algorithm 394

Swarm Simulation 394

Boids 395

Pseudoclassical Mechanics 396

Goals and Obstacles 397

Summary 397

Exercises 398

Chapter 13 Basic Network Algorithms 403

Network Terminology 403

Network Representations 407

Traversals 409

Depth-First Traversal 410

Breadth-First Traversal 412

Connectivity Testing 413

Spanning Trees 416

Minimal Spanning Trees 417

Euclidean Minimum Spanning Trees 418

Building Mazes 419

Strongly Connected Components 420

Kosaraju's Algorithm 421

Algorithm Discussion 422

Finding Paths 425

Finding Any Path 425

Label-Setting Shortest Paths 426

Label-Correcting Shortest Paths 430

All-Pairs Shortest Paths 431

Transitivity 436

Transitive Closure 437

Transitive Reduction 438

Acyclic Networks 439

General Networks 440

Shortest Path Modifications 441

Shape Points 441

Early Stopping 442

Bidirectional Search 442

Best-First Search 442

Turn Penalties and Prohibitions 443

Geometric Calculations 443

Expanded Node Networks 444

Interchange Networks 445

Summary 447

Exercises 447

Chapter 14 More Network Algorithms 451

Topological Sorting 451

Cycle Detection 455

Map Coloring 456

Two-Coloring 456

Three-Coloring 458

Four-Coloring 459

Five-Coloring 459

Other Map-Coloring Algorithms 462

Maximal Flow 464

Work Assignment 467

Minimal Flow Cut 468

Network Cloning 470

Dictionaries 471

Clone References 472

Cliques 473

Brute Force 474

Bron-Kerbosch 475

Sets R, P, and X 475

Recursive Calls 476

Pseudocode 476

Example 477

Variations 480

Finding Triangles 480

Brute Force 481

Checking Local Links 481

Chiba and Nishizeki 482

Community Detection 483

Maximal Cliques 483

Girvan-Newman 483

Clique Percolation 485

Eulerian Paths and Cycles 485

Brute Force 486

Fleury's Algorithm 486

Hierholzer's Algorithm 487

Summary 488

Exercises 489

Chapter 15 String Algorithms 493

Matching Parentheses 494

Evaluating Arithmetic Expressions 495

Building Parse Trees 496

Pattern Matching 497

DFAs 497

Building DFAs for Regular Expressions 500

NFAs 502

String Searching 504

Calculating Edit Distance 508

Phonetic Algorithms 511

Soundex 511

Metaphone 513

Summary 514

Exercises 515

Chapter 16 Cryptography 519

Terminology 520

Transposition Ciphers 521

Row/Column Transposition 521

Column Transposition 523

Route Ciphers 525

Substitution Ciphers 526

Caesar Substitution 526

Vigenere Cipher 527

Simple Substitution 529

One-Time Pads 530

Block Ciphers 531

Substitution-Permutation Networks 531

Feistel Ciphers 533

Public-Key Encryption and RSA 534

Euler's Totient Function 535

Multiplicative Inverses 536

An RSA Example 536

Practical Considerations 537

Other Uses for Cryptography 538

Summary 539

Exercises 540

Chapter 17 Complexity Theory 543

Notation 544

Complexity Classes 545

Reductions 548

3SAT 549

Bipartite Matching 550

NP-Hardness 550

Detection, Reporting, and Optimization Problems 551

Detection <=p Reporting 552

Reporting <=p Optimization 552

Reporting <=p Detection 552

Optimization <=p Reporting 553

Approximate Optimization 553

NP-Complete Problems 554

Summary 557

Exercises 558

Chapter 18 Distributed Algorithms 561

Types of Parallelism 562

Systolic Arrays 562

Distributed Computing 565

Multi-CPU Processing 567

Race Conditions 567

Deadlock 571

Quantum Computing 572

Distributed Algorithms 573

Debugging Distributed Algorithms 573

Embarrassingly Parallel Algorithms 574

Mergesort 576

Dining Philosophers 577

Randomization 578

Resource Hierarchy 578

Waiter 579

Chandy/Misra 579

The Two Generals Problem 580

Byzantine Generals 581

Consensus 584

Leader Election 587

Snapshot 588

Clock Synchronization 589

Summary 591

Exercises 591

Chapter 19 Interview Puzzles 595

Asking Interview Puzzle Questions 597

Answering Interview Puzzle Questions 598

Summary 602

Exercises 604

Appendix A Summary of Algorithmic Concepts 607

Chapter 1: Algorithm Basics 607

Chapter 2: Numeric Algorithms 608

Chapter 3: Linked Lists 609

Chapter 4: Arrays 610

Chapter 5: Stacks and Queues 610

Chapter 6: Sorting 610

Chapter 7: Searching 611

Chapter 8: Hash Tables 612

Chapter 9: Recursion 612

Chapter 10: Trees 614

Chapter 11: Balanced Trees 615

Chapter 12: Decision Trees 615

Chapter 13: Basic Network Algorithms 616

Chapter 14: More Network Algorithms 617

Chapter 15: String Algorithms 618

Chapter 16: Cryptography 618

Chapter 17: Complexity Theory 619

Chapter 18: Distributed Algorithms 620

Chapter 19: Interview Puzzles 621

Appendix B Solutions to Exercises 623

Chapter 1: Algorithm Basics 623

Chapter 2: Numerical Algorithms 626

Chapter 3: Linked Lists 633

Chapter 4: Arrays 638

Chapter 5: Stacks and Queues 648

Chapter 6: Sorting 650

Chapter 7: Searching 653

Chapter 8: Hash Tables 655

Chapter 9: Recursion 658

Chapter 10: Trees 663

Chapter 11: Balanced Trees 670

Chapter 12: Decision Trees 675

Chapter 13: Basic Network Algorithms 678

Chapter 14: More Network Algorithms 681

Chapter 15: String Algorithms 686

Chapter 16: Encryption 689

Chapter 17: Complexity Theory 692

Chapter 18: Distributed Algorithms 697

Chapter 19: Interview Puzzles 701

Glossary 711

Index 739