Grokking Algorithms (MEAP v4) 2ed 2023

Grokking Algorithms, Second Edition MEAP V01
Copyright
Welcome
Brief contents
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
Exercises
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
Exercises
The traveling salesperson
Recap
Chapter 2: Selection sort
How memory works
Arrays and linked lists
Linked lists
Arrays
Terminology
Exercise
Inserting into the middle of a list
Deletions
Exercises
Selection sort
Example code listing
Recap
Chapter 3: Recursion
Recursion
Base case and recursive case
The stack
The call stack
Exercise
The call stack with recursion
Exercise
Recap
Chapter 4: Quicksort
Divide & conquer
Exercises
Quicksort
Big O notation revisited
Merge sort vs. quicksort
Average case vs. worst case
Exercises
Recap
Chapter 5: Hash tables
Hash functions
Exercises
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
Exercises
Recap
Chapter 6: Breadth-first search
Introduction to graphs
What is a graph?
Breadth-first search
Finding the shortest path
Queues
Exercises
Implementing the graph
Implementing the algorithm
Running time
Exercise
Recap
Chapter 7: Trees
Your first tree
File Directories
A Space Odyssey: depth-first search
A better definition of trees
Binary trees
Huffman coding
Recap
A balancing act
Improving insertion speed with trees
Balanced trees
AVL Trees — a type of balanced tree
Rotations
How does the AVL tree know when it's time to rotate?
Splay Trees
B-Trees
So what is the advantage of B-trees?
Recap
Working with Dijkstra’s algorithm
Terminology
Trading for a piano
Negative-weight edges
Implementation
Exercise
Recap
Chapter 10: Greedy algorithms
The classroom scheduling problem
The knapsack problem
Exercises
The set-covering problem
Approximation algorithms
NP-hard problems
Decision Problems
The satisfiability (SAT) problem
Hard to solve, quick to verify
Reductions
NP Hard
NP-complete
Recap
Chapter 11: Dynamic programming
The knapsack problem (revisited)
The simple solution
Dynamic programming
Knapsack problem FAQ
What happens if you add an item?
Exercise
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?
Exercise
Longest common substring
Making the grid
Filling in the grid
The solution
Longest common subsequence
Longest common subsequence—solution
Exercise
Recap
Classifying oranges vs. grapefruit
Building a recommendations system
Feature extraction
Exercises
Regression
Picking good features
Exercise
Introduction to machine learning
OCR
Building a spam filter
Predicting the stock market
Recap