What you will learn in Grokking Algorithms, Second Edition
Chapter by chapter
Chapter 1: Introduction to algorithms
The introduction defines an algorithm and explains why the book focuses on algorithms that speed up tasks or solve interesting problems.
What you learn in chapter 1 →Chapter 2: Selection sort
The chapter introduction explains why sorted data matters and why learning selection sort is worthwhile even when sorting is built in.
What you learn in chapter 2 →Chapter 3: Recursion
The chapter introduces recursion’s importance, recommends hands-on ways to learn it, and defines pseudocode.
What you learn in chapter 3 →Chapter 4: Quicksort
The introduction presents divide and conquer as a reusable recursive technique to consider when familiar algorithms do not solve a new problem.
What you learn in chapter 4 →Chapter 5: Hash tables
The grocery-store price lookup example compares search speeds and motivates the need for hash tables.
What you learn in chapter 5 →Chapter 6: Breadth-first search
The chapter introduction presents breadth-first search as a way to find shortest distances and shows that “shortest” can mean different things in different applications.
What you learn in chapter 6 →Chapter 7: Trees
The introduction places trees within graphs and shows why specialized trees matter for compression and database storage.
What you learn in chapter 7 →Chapter 8: Balanced trees
The chapter introduction motivates balanced trees as a way to improve tree performance when other data structures fall short.
What you learn in chapter 8 →Chapter 9: Dijkstra’s algorithm
This introduction contrasts finding the path with the fewest segments with finding the fastest path when graph edges have travel times.
What you learn in chapter 9 →Chapter 10: Greedy algorithms
The chapter introduction previews greedy strategies, NP-hard problems, and approximation algorithms.
What you learn in chapter 10 →Chapter 11: Dynamic programming
The introduction defines dynamic programming as solving a hard problem by first solving smaller subproblems.
What you learn in chapter 11 →Chapter 12: k-nearest neighbors
This chapter introduction previews classification with k-nearest neighbors, feature extraction, regression, and the algorithm’s uses and limitations.
What you learn in chapter 12 →Chapter 13: Where to go next
The chapter previews brief introductions to additional algorithms and suggests further reading based on the reader’s interests.
What you learn in chapter 13 →Concepts explained in this book
- MapA dictionary is a Python mapping data structure that associates keys with corresponding values.
- treeA tree is a connected graph with no cycles, so no path of edges leads back to an earlier vertex.
- Dijkstra's algorithmDijkstra's algorithm is a graph shortest-path algorithm that repeatedly selects the lowest-cost unprocessed node and relaxes its outgoing edges, assuming edge weights are nonnegative.
- breadth-first searchBreadth-first search is a graph-search algorithm that explores vertices in increasing order of their distance from a starting vertex.
- hash functionA hash function is a deterministic function that maps a key to a value used to determine its storage location in a hash table.
- linked listA linked list is an ordered data structure whose items store links to the addresses of subsequent items rather than occupying adjacent memory locations.
- arrayAn array is a data structure that stores elements in indexed positions, typically in contiguous memory.
- dynamic programmingDynamic programming is an algorithmic technique that solves overlapping subproblems by storing and reusing their results.
- divide-and-conquer approachA divide-and-conquer strategy solves a problem by dividing it into smaller subproblems, solving those subproblems, and combining their results.
- performanceBig O notation is a mathematical notation for describing the asymptotic growth rate of an algorithm's resource usage as input size increases.
- stopping criterionA base case is the terminating condition of a recursive definition or function that can be solved without another recursive invocation.
- binary treeA binary tree is a tree in which each node has at most two children.
- graphA graph is a data structure consisting of nodes and connections that represent relationships between entities.
- edge weightAn edge weight is a numerical value assigned to a graph edge to represent traversal cost, distance, time, or another quantity.
- recursionRecursion is a problem-solving technique in which a procedure solves a problem by invoking itself on smaller or simpler instances of that problem.
- binary searchAn algorithm that searches a sorted list by repeatedly narrowing the search interval and returns the position of a matching element or null when no match exists.
- gridA tabular arrangement of cells that stores computed values for different knapsack capacities.
- subproblemA subproblem is a smaller instance of a larger computational problem whose solution contributes to solving the larger instance.
- quicksortQuicksort is a comparison-based sorting algorithm that partitions a sequence around a pivot and recursively sorts the partitions.
- knapsack problemThe knapsack problem is an optimization problem that selects items within a capacity constraint to maximize their combined value.
- Huffman encodingHuffman coding is a lossless compression algorithm that represents more frequent symbols with shorter variable-length codes.
- costA cost is a numerical amount representing the time, distance, or other expense associated with reaching a node or traversing an edge.
- inputA feature is an observable attribute or input variable used to characterize an item for comparison or prediction.
- leaf nodeA leaf node is a node in a tree that has no children.
- pivotA pivot is an element selected from a sequence to divide the other elements into groups during partitioning.
- quadratic time complexityO(n2) is a quadratic time-complexity bound whose operation count grows with the square of the input size.
- encodingA character encoding is a system that represents text characters as binary code values.
- execution context stackA call stack is a runtime stack that stores information for active function calls, including their execution state and local data.
- setA set is a collection that stores distinct elements without assigning significance to their insertion order.
- logarithmic time complexityLogarithmic time describes an algorithmic running time that grows in proportion to the logarithm of the input size.
- linear time complexityLinear time describes an algorithmic running time that grows proportionally with the size of the input.
- simple searchSimple search is a sequential search technique that checks elements one at a time until the target is found or the sequence is exhausted.
- greedy algorithmA greedy algorithm constructs a solution by repeatedly making locally best choices without generally reconsidering earlier choices.
- hash collisionA hash collision occurs when distinct keys produce the same hash value or table position.
- O(n * log n)O(n * log n) is a time-complexity bound whose operation count grows as the input size multiplied by its logarithm.
- shortest pathA shortest-path problem asks for a path between locations or nodes that minimizes the number of steps or another path cost.
- binary search treeA binary search tree is a binary tree whose nodes are ordered so that values in the left subtree precede the node's value and values in the right subtree follow it.
- AVL treeAn AVL tree is a self-balancing binary search tree that maintains subtree heights within a bounded difference by performing rotations.
- tree heightTree height is the maximum number of edges or steps on a downward path from the root to a leaf or other node.
- random accessRandom access is the ability to retrieve an element directly by its position without sequentially traversing preceding elements.
- tree rotationA tree rotation is a local restructuring operation that changes parent-child relationships while preserving the tree's ordering.
- rooted treeA rooted tree is a tree with one distinguished root node from which traversal begins.
- sorting algorithmA sorting algorithm is an algorithm that arranges elements according to an ordering criterion.
- parent pointerA parent pointer is a recorded predecessor node that identifies the preceding step in a path to another node.
- average-case analysisAn average-case runtime is the expected execution time of an algorithm over a specified distribution of inputs of a given size.
- worst-case performanceThe worst-case scenario is the execution situation in which an algorithm requires its maximum runtime for inputs of a specified size.
- sequential accessSequential access is an access pattern that retrieves elements in order by traversing from the beginning of a sequence.
- dataset splitPartitioning is the process of dividing a sequence around a selected pivot into groups based on their comparison with the pivot.
- inductive proofAn inductive proof is a proof method that establishes a statement for a base case and then proves that validity for one case implies validity for the next case.
- edgeAn edge is a connection between two vertices in a graph, optionally representing a direction from one vertex to another.
- UnicodeUnicode is a character encoding standard that assigns code points to characters across writing systems.
- UTF-8UTF-8 is a variable-length character encoding for representing Unicode text using one to four bytes per character.
- optimal solutionAn optimal solution is a feasible solution that achieves the best possible objective value for an optimization problem.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.