Essential Algorithms: A Practical Approach to Computer Algorithms
Essential Algorithms: A Practical Approach to Computer Algorithms
ISBN: 9781118612101
Aug 2013
624 pages
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 advanced data structures such as heaps, 23 trees, Btrees
 Addresses general problemsolving 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 problemsolving 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
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
LinkedList 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
Onedimensional 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
LinkedList Stacks 112
Array Stacks 113
Double Stacks 115
Stack Algorithms 117
Queues 123
LinkedList 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
Depthfirst 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
23 Trees 282
Adding Values 283
Deleting Values 284
BTrees 287
Adding Values 288
Deleting Values 289
Balanced Tree Variations 291
Topdown Btrees 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
Depthfirst Traversal 331
Breadthfirst Traversal 334
Connectivity Testing 335
Spanning Trees 337
Minimal Spanning Trees 338
Finding Paths 339
Finding Any Path 339
LabelSetting Shortest Paths 340
LabelCorrecting Shortest Paths 344
AllPairs Shortest Paths 345
Summary 350
Exercises 351
Chapter 14 More Network Algorithms 355
Topological Sorting 355
Cycle Detection 359
Map Coloring 359
Twocoloring 360
Threecoloring 362
Fourcoloring 362
Fivecoloring 363
Other Mapcoloring 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
OneTime Pads 408
Block Ciphers 408
SubstitutionPermutation Networks 409
Feistel Ciphers 410
PublicKey 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
NPHardness 426
Detection, Reporting, and Optimization Problems 427
Detection ≤p Reporting 427
Reporting ≤p Optimization 428
Reporting ≤p Detection 428
Optimization ≤p
Reporting 429
NPComplete Problems 429
Summary 431
Exercises 432
Chapter 18 Distributed Algorithms 435
Types of Parallelism 436
Systolic Arrays 436
Distributed Computing 438
MultiCPU 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
Chapter  Page  Details  Date  Print 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,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.)  09/20/2013  
32  Errata in Text,Text currently reads: inside the box A Fairly Random Array , the calculation printed in large test before the penultimate paragraph ends with (N1)/(N(k1)), it should be 1/(N(k1)) as the probability of Pk defined in the general case a few lines above as Pi = 1/(Ni1). 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(k1)).  11Oct16  
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. 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.  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, np1 Mod p = 1. This should say: Fermat's little theorem states that if p is prime and 1 ≤ n < p, np1 Mod p = 1.  09/20/2013  
53  Error 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.  09/20/2013  
53  Error in Text,The solution to Exercise 14 (the CarmichaelNumbers progr
