Content

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

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

3. Recursion

• Recursion
• Base case and recursive case
• The stack

  • The call stack
  • The call stack with recursion
• Recap

4. Quicksort

• Divide & conquer
• Quicksort
• Big O notation revisited

  • Merge sort vs. quicksort
  • Average case vs. worst case
• Recap

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

6. Breadth-first search

• Introduction to graph
• What is a graph
• Breadth-first search

  • Finding the shortes path
  • Queues
• Implementing the graph
• Implementing the algorithm

  • Running time
• Recap

7. Dijkstra's algorithm

• Working with Dijkstra's algorithm
• Terminology
• Trading for a piano
• Negative-weight edges
• Implementation
• Recap

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

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 instead of 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 require more than two sub-knapsacks?
  • Is it possible that the best solution doesn't fill the knapsack completely?
• Longest common substring

  • Making the grid
  • Filling in the grid
  • The solution
  • Longest common subsequence
  • Longest common subsequence—solution
• Recap

10. K-nearest neighbors

• 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

11. Where to go next

• Trees
• Inverted indexes
• The Fourier transform
• Parallel algorithms
• MapReduce

  • Why are distributed algorithms useful?
  • 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

• Chapter 10