Essential algorithms : a practical approach to computer algorithms using Python and C# / Rod Stephens.

Language: English Publisher: Indianapolis, IN : Wiley, [2019]Description: 1 online resource (xxxviii, 762 pages)Content type: text Media type: computer Carrier type: online resourceISBN: 9781119575993 Subject(s): Computer algorithms | Python (Computer program language) | C# (Computer program language)Genre/Form: Electronic books.DDC classification: 005.1 Online resources: Full text available at Wiley Online Library Click here to view
Contents:
TABLE OF CONTENTS Introduction xxix 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 N2 15 2N 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(N2 ) 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 Sierpiński 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
Summary: 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++).
Tags from this library: No tags from this library for this title. Log in to add tags.
    Average rating: 0.0 (0 votes)
Item type Current location Home library Call number Status Date due Barcode Item holds
EBOOK EBOOK COLLEGE LIBRARY
COLLEGE LIBRARY
005.1 Es742 2019 (Browse shelf) Available CL-50938
Total holds: 0

ABOUT THE AUTHOR
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 more than 30 books that have been translated into nearly a dozen languages.

TABLE OF CONTENTS
Introduction xxix

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

N2 15

2N 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(N2 ) 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

Sierpiński 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

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

There are no comments for this item.

to post a comment.