Absolute Beginner's Guide to Algorithms, 1st edition

Part I: Data Structures

 

Chapter 1. Introduction to Data Structures .................................................................. 1

     Right Tool for the Right Job .................................................................................... 2

     Back to Data Structures ........................................................................................... 5

     Conclusion ................................................................................................................. 6

 

Chapter 2. Big-O Notation and Complexity Analysis ................................................... 7

     It's Example Time ...................................................................................................... 8

     It's Big-O Notation Time! .......................................................................................11

     Conclusion ...............................................................................................................15

 

Chapter 3. Arrays ....................................................................................................... 17

     What Is an Array? ....................................................................................................18

     Array Implementation / Use Cases .......................................................................24

     Arrays and Memory ................................................................................................26

     Performance Considerations .................................................................................30

     Conclusion ...............................................................................................................32

 

Chapter 4. Linked Lists ............................................................................................... 35

     Meet the Linked List ...............................................................................................36

     Linked List: Time and Space Complexity .............................................................40

     Linked List Variations ..............................................................................................41

     Implementation .......................................................................................................44

     Conclusion ...............................................................................................................52

 

Chapter 5. Stacks ........................................................................................................ 53

     Meet the Stack ........................................................................................................54

     A JavaScript Implementation ................................................................................56

     Stacks: Time and Space Complexity ....................................................................58

     Conclusion ...............................................................................................................59

 

Chapter 6. Queues ..................................................................................................... 61

     Meet the Queue .....................................................................................................62

     A JavaScript Implementation ................................................................................64

     Queues: Time and Space Complexity ..................................................................66

     Conclusion ...............................................................................................................67

 

Chapter 7. Trees ......................................................................................................... 69

     Trees 101 .................................................................................................................70

     Height and Depth ...................................................................................................75

     Conclusion ...............................................................................................................77

 

Chapter 8. Binary Trees .............................................................................................. 79

     Meet the Binary Tree ..............................................................................................80

     A Simple Binary Tree Implementation ..................................................................86

     Conclusion ...............................................................................................................89

 

Chapter 9. Binary Search Trees ................................................................................... 91

     It's Just a Data Structure ........................................................................................93

     Implementing a Binary Search Tree ....................................................................103

     Performance and Memory Characteristics .........................................................110

     Conclusion .............................................................................................................112

 

Chapter 10. Heaps ...................................................................................................... 113

     Meet the Heap ......................................................................................................114

     Heap Implementation ..........................................................................................126

     Performance Characteristics ................................................................................132

     Conclusion .............................................................................................................134

 

Chapter 11. Hashtable (aka Hashmap or Dictionary) .................................................. 137

     A Very Efficient Robot ..........................................................................................138

     From Robots to Hashing Functions ....................................................................142

     From Hashing Functions to Hashtables .............................................................145

     JavaScript Implementation/Usage ......................................................................148

     Dealing with Collisions .........................................................................................150

     Performance and Memory ...................................................................................151

     Conclusion .............................................................................................................153

 

Chapter 12. Trie (aka Prefix Tree) ............................................................................... 155

     What Is a Trie? ......................................................................................................156

     Diving Deeper into Tries ......................................................................................167

     Many More Examples Abound! ..........................................................................172

     Implementation Time ...........................................................................................173

     Performance ..........................................................................................................179

     Conclusion .............................................................................................................181

 

Chapter 13. Graphs .................................................................................................... 183

     What Is a Graph? ..................................................................................................184

     Graph Implementation .........................................................................................190

     Conclusion .............................................................................................................196

 

Part II: Algorithms

 

Chapter 14. Introduction to Recursion ....................................................................... 199

     Our Giant Cookie Problem ..................................................................................200

     Recursion in Programming ..................................................................................202

     Conclusion .............................................................................................................206

 

Chapter 15. Fibonacci and Going Beyond Recursion ................................................. 207

     Recursively Solving the Fibonacci Sequence ....................................................209

     Recursion with Memoization ...............................................................................213

     Taking an Iteration-Based Approach ..................................................................215

     Going Deeper on the Speed ..............................................................................217

     Conclusion .............................................................................................................218

 

Chapter 16. Towers of Hanoi ...................................................................................... 221

     How Towers of Hanoi Is Played ..........................................................................222

     The Single Disk Case ...........................................................................................223

     It's Two Disk Time .................................................................................................224

     Three Disks ............................................................................................................225

     The Algorithm .......................................................................................................228

     The Code Solution ...............................................................................................229

     Check Out the Recursiveness! ............................................................................231

     It's Math Time ........................................................................................................232

     Conclusion .............................................................................................................234

 

Chapter 17. Search Algorithms and Linear Search ..................................................... 235

     Linear Search .........................................................................................................236

     Conclusion .............................................................................................................241

 

Chapter 18. Faster Searching with Binary Search ....................................................... 243

     Binary Search in Action ........................................................................................243

     The JavaScript Implementation ..........................................................................250

     Runtime Performance ...........................................................................................254

     Conclusion .............................................................................................................257

 

Chapter 19. Binary Tree Traversal ............................................................................... 259

     Breadth-First Traversal ..........................................................................................260

     Depth-First Traversal ............................................................................................265

     Implementing Our Traversal Approaches ..........................................................270

     Performance of Our Traversal Approaches ........................................................278

     Conclusion .............................................................................................................279

 

Chapter 20. Depth-First Search (DFS) and Breadth-First Search (BFS) ....................... 281

     A Tale of Two Exploration Approaches ..............................................................282

     It's Example Time ..................................................................................................285

     When to Use DFS? When to Use BFS? ..............................................................298

     A JavaScript Implementation ..............................................................................300

     Performance Details .............................................................................................307

     Conclusion .............................................................................................................308

 

Chapter 21. Quicksort ................................................................................................ 309

     A Look at How Quicksort Works .........................................................................310

     Another Simple Look ...........................................................................................314

     It's Implementation Time .....................................................................................319

     Performance Characteristics ................................................................................322

     Conclusion .............................................................................................................323

 

Chapter 22. Bubblesort .............................................................................................. 325

     How Bubblesort Works ........................................................................................326

     Walkthrough ..........................................................................................................329

     The Code ...............................................................................................................333

     Conclusion .............................................................................................................333

 

Chapter 23. Insertion Sort .......................................................................................... 335

     How Insertion Sort Works ....................................................................................336

     One More Example ..............................................................................................347

     Algorithm Overview and Implementation .........................................................349

     Performance Analysis ...........................................................................................351

     Conclusion .............................................................................................................353

 

Chapter 24. Selection Sort ......................................................................................... 355

     Selection Sort Walkthrough .................................................................................356

     Algorithm Deep Dive ...........................................................................................364

     The JavaScript Implementation ..........................................................................366

     Conclusion .............................................................................................................369

 

Chapter 25. Mergesort ............................................................................................... 371

     How Mergesort Works .........................................................................................372

     Mergesort: The Algorithm Details ......................................................................379

     Looking at the Code ............................................................................................380

     Conclusion .............................................................................................................381

 

Conclusion .................................................................................................................383

 

Index ............................................................................................................................ 387