Skip to main content

Essential Algorithms: A Practical Approach to Computer Algorithms

Essential Algorithms: A Practical Approach to Computer Algorithms

Rod Stephens

ISBN: 978-1-118-61210-1 August 2013 624 Pages


In Stock



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.

Related Resources

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

Complete code downloads for Essential Algorithms
Updated 7/19/13
P2P Forum on Site
P2P Forum
ChapterPageDetailsDatePrint Run
12Error in Text
The end of the first paragraph after the "Logarythms" box currently reads:
It's a sorted tree because every node's value lies between the values of its left and right child nodes.

It is true that a sorted tree has this property but more precisely the text should say:
It's a sorted tree because every node's value is at least as large as its left child and no larger than its right child.

14Error in Text
The fourth paragraph currently reads:
A full complete binary tree of height H has 2H nodes.

This text was trying to be approximate so it should have said:
The tree has approximately 2H nodes.

More precisely a full complete binary tree of height H has 2H+1 - 1 nodes. (This fact is mentioned in the second bullet point on page 232.) Given this change, the sentence that follows on page 14 should also be corrected. Again if you're looking at Big O notation, a full complete binary tree containing N nodes has height roughly log2(N). More precisely the height is log2(N + 1) - 1. (See the third bullet point on page 232.)

32Errata in Text
Text currently reads:
inside the box "A Fairly Random Array", the calculation printed in large test before the penultimate paragraph ends with (N-1)/(N-(k-1)), it should be 1/(N-(k-1)) as the probability of Pk defined in the general case a few lines above as Pi = 1/(N-i-1). As it stands, the claimed simplification to 1/N is not mathematically correct when based on the printed calculation, when it should be, the printed calculation simply being wrong.
This is correct. It was that way in the original text and got changed somewhere along the way to print. I suggest the follow erratum:
Text should read:
in the box "A Fairly Random Array." The last term in large equation should be 1/(N-(k-1)).

236Error in Text
The fourth paragraph on the page begins:
More generally, for the exponent P, the algorithm calculates log(P) powers of A. It then examines the binary digits of A to see which of those powers it must multiply together to get the final result.

This should read:
More generally, for the exponent P, the algorithm calculates log(P) powers of A. It then examines the binary digits of P to see which of those powers it must multiply together to get the final result.

39Error in Code
The FindPrimes algorithm uses this code:
While (next_prime < stop_at)

This should be:
While (next_prime <= stop_at)

40Error in Text
The fourth paragraph in the section "Testing for Primality" currently reads:
Fermat's "little theorem" states that if p is prime and 1 ≤ n ≤ p, np-1 Mod p = 1.

This should say:
Fermat's "little theorem" states that if p is prime and 1 ≤ n < p, np-1 Mod p = 1.

53Error in Text
Exercise 14 currently reads:
In an infinite set of composite numbers called Carmichael numbers, every relatively prime smaller number is a Fermat liar. In other words, p is a Carmichael number if every n where 1 ≤ n ≤ p and GCD(p, n) = 1 is a Fermat liar.

This should read:
In an infinite set of odd composite numbers called Carmichael numbers, every relatively prime smaller number is a Fermat liar. In other words, p is a Carmichael number if p is odd and every n where 1 < n < p and GCD(p, n) = 1 is a Fermat liar.

53Error in Text
The solution to Exercise 14 (the CarmichaelNumbers program)
Currently reads:
    // Check for Carmichael numbers.
    for (int i = 2; i < maxNumber; i++)

Should be the following (to check for only odd Carmichael numbers):
    // Check for Carmichael numbers.
    for (int i = 3; i < maxNumber; i += 2)

53Error in Text
Inside the IsCarmichael method:

Currently reads:
    // Check all possible witnesses.
    for (int i = 1; i < number - 1; i++)

Should be this:
    // Check all possible witnesses.
    for (int i = 2; i < number; i++)

238Text Correction
First sentence on page 238 of the print edition reads:
Binary trees have four kinds of traversals: preorder, inorder, postorder, and depth-first. This should be:
Binary trees have four kinds of traversals: preorder, inorder, postorder, and breadth-first.

10243Error in Text
Throughout this section, depth-first traversal should be breadth-first traversal. A breadth-first traversal visits all of the nodes across the breadth of one level before moving down to the next level in the tree. All of the other algorithms (preorder, inorder, and postorder) are actually depth-first traversals.

487Errata in Text
Text currently reads:
Table B-1, Column SQRT(n), Row Week, the value 4x10^11 is obviously incorrect given the value immediately above it. I believe it should be about 4.9*10^22 (i.e. 7 times the value for the Days row), round as you will.
This is correct. I recommend the following erratum:
Text should read:
in Table B-1 the second entry in the "Week" row should be 4x10^23.

App B488Error in Text
The solution to exercise 1-3 has the roles of the two algorithms are reversed. The correct solution should be:
The question is, "For what N is 1,500 ? N > 30 ? N2?" Solving for N gives 50 < N, so the second algorithm is slower if N > 50. You would use the second algorithm if N ≤ 50 and the first if N > 50.