Absolute Beginner's Guide to Algorithms

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