# Essential Algorithms: A Practical Approach to Computer Algorithms

ISBN: 978-1-118-61210-1
624 pages
August 2013
For Instructors

## Description

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

See More

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

Monte Carlo Integration 48

Finding Zeros 49

Summary 51

Exercises 52

Basic Concepts 55

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

Copying Lists 67

Sorting with Insertionsort 68

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

Array Stacks 113

Double Stacks 115

Stack Algorithms 117

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

Removing Items 174

Liner Probing 174

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

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

Finding Nodes 247

Deleting Nodes 248

Specialized Tree Algorithms 256

The Animal Game 256

Expression Evaluation 258

Tries 266

Summary 270

Exercises 271

Chapter 11 Balanced Trees 277

AVL Trees 278

Deleting Values 281

2-3 Trees 282

Deleting Values 284

B-Trees 287

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

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

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

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

Snapshot 459

Clock Synchronization 460

Summary 462

Exercises 462

Chapter 19 Interview Puzzles 465

Summary 472

Exercises 474

Appendix A Summary of Algorithmic Concepts 477

Appendix B Solutions to Exercises 487

Glossary 559

Index 573

See More

## Author Information

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.

See More

Updated 7/19/13
P2P Forum on Wrox.com Site
P2P Forum

See More

## Errata

Do you think you've discovered an error in this book? Please check the list of errata below to see if we've already addressed the error. If not, please submit the error via our Errata Form. We will attempt to verify your error; if you're right, we will post a correction below.

ChapterPageDetailsDatePrint Run
12 Error 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.
09/20/2013
14 Error in Text
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.)
09/20/2013
32 Errata in Text
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:
in the box "A Fairly Random Array." The last term in large equation should be 1/(N-(k-1)).
11-Oct-16
2 36 Error 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.

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.
09/05/2013
39 Error in Code
The FindPrimes algorithm uses this code:
While (next_prime < stop_at)

This should be:
While (next_prime <= stop_at)
09/20/2013
40 Error 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.
09/20/2013
53 Error in Text
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.

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.
09/20/2013
53 Error in Text
The solution to Exercise 14 (the CarmichaelNumbers program)
```
// 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)
```
09/20/2013
53 Error in Text
Inside the IsCarmichael method:

```
// 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++)
```
09/20/2013
238 Text 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.
04/02/15
10 243 Error 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.
09/05/2013
487 Errata in Text
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:
in Table B-1 the second entry in the "Week" row should be 4x10^23.
App B 488 Error 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.
09/05/2013
See More
Instructors Resources
Wiley Instructor Companion Site
Request a print evaluation copy