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