Grokking Algorithms

T
third-degree connection 103
topological sort 112
training 200
trees 203–206
U
undirected graph 122
unique searches 213
unweighted graph 120
W
weighted graph 120
i
ndex

---

---

Document Outline

• Cover
• contents
• preface
• acknowledgments
• about this book
• Chapter 1 Introduction to Algorithms
  • Introduction
    • What you’ll learn about performance
    • What you’ll learn about solving problems
  • Binary search
    • A better way to search
    • Running time
  • Big O notation
    • Algorithm running times grow at different rates
    • Visualizing different Big O run times
    • Big O establishes a worst-case run time
    • Some common Big O run times
    • The traveling salesperson
  • Recap
• Chapter 2 Selection Sort
  • How memory works
  • Arrays and linked lists
    • Linked lists
    • Arrays
    • Terminology
    • Inserting into the middle of a list
    • Deletions
  • Selection sort
  • Recap
• Chapter 3 Recursion
  • Recursion
  • Base case and recursive case
  • The stack
    • The call stack
    • The call stack with recursion
  • Recap
• Chapter 4 Quicksort
  • Divide & conquer
  • Quicksort
  • Big O notation revisited
    • Merge sort vs. quicksort
    • Average case vs. worst case
  • Recap
• Chapter 5 Hash Tables
  • Hash functions
  • Use cases
    • Using hash tables for lookups
    • Preventing duplicate entries
    • Using hash tables as a cache
    • Recap
  • Collisions
  • Performance
    • Load factor
    • A good hash function
  • Recap
• Chapter 6 Breadth-First Search
  • Introduction to graphs
  • What is a graph?
  • Breadth-first search
    • Finding the shortest path
    • Queues
  • Implementing the graph
  • Implementing the algorithm
    • Running time
  • Recap
• Chapter 7 Dijkstra’s Algorithm
  • Working with Dijkstra’s algorithm
  • Terminology
  • Trading for a piano
  • Negative-weight edges
  • Implementation
  • Recap
• Chapter 8 Greedy Algorithms
  • The classroom scheduling problem
  • The knapsack problem
  • The set-covering problem
    • Approximation algorithms
  • NP-complete problems
  • Traveling salesperson, step by step
    • How do you tell if a problem is NP-complete?
  • Recap
• Chapter 9 Dynamic Programming
  • The knapsack problem
    • The simple solution
    • Dynamic programming
  • Knapsack problem FAQ
    • What happens if you add an item?
    • What happens if you change the order of the rows?
    • Can you fill in the grid column-wise insteadof row-wise?
    • What happens if you add a smaller item?
    • Can you steal fractions of an item?
    • Optimizing your travel itinerary
    • Handling items that depend on each other
    • Is it possible that the solution will requiremore than two sub-knapsacks?
    • Is it possible that the best solution doesn’tfill the knapsack completely?
  • Longest common substring
    • Making the grid
    • Filling in the grid
    • The solution
    • Longest common subsequence
    • Longest common subsequence—solution
  • Recap
• Chapter 10 K-nearestneighbors
  • Classifying oranges vs. grapefruit
  • Building a recommendations system
    • Feature extraction
    • Regression
    • Picking good features
  • Introduction to machine learning
    • OCR
    • Building a spam filter
    • Predicting the stock market
  • Recap
• Chapter 11 Where to Go Next
  • Trees
  • Inverted indexes
  • The Fourier transform
  • Parallel algorithms
  • MapReduce
    • Why are distributed algorithms usefule?
    • The map function
    • The reduce function
  • Bloom filters and HyperLogLog
    • Bloom filters
    • HyperLogLog
  • The SHA algorithms
    • Comparing files
    • Checking passwords
  • Locality-sensitive hashing
  • Diffie-Hellman key exchange
  • Linear programming
  • Epilogue
• Answers to Exercises
  • CHAPTER 1
  • CHAPTER 2
  • CHAPTER 3
  • CHAPTER 4
  • CHAPTER 5
  • CHAPTER 6
  • CHAPTER 7
  • CHAPTER 8
  • CHAPTER 9
  • CHPATER 10
• Index
  • A
  • B
  • C
  • D
  • E
  • F
  • G
  • H
  • I
  • J
  • K
  • L
  • M
  • N
  • O
  • P
  • Q
  • R
  • S
  • T
  • U
  • W