# Essential Algorithms: A Practical Approach to Computer Algorithms

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

Paperback

In Stock

\$60.00

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

## Related Resources

### Instructor

Request an Evaluation Copy for this title

View Instructor Companion Site

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

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.
09/20/2013

14Error 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

32Errata 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

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.

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

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

This should be:
While (next_prime <= stop_at)
09/20/2013

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.
09/20/2013

53Error 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

53Error 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

53Error 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

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.
04/02/15

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.
09/05/2013

487Errata in Text