Chapter 1: The Language of Algorithms
This introduction explains why algorithms matter in everyday software and why choosing one requires practical judgment, not just a search for theoretical optimality.
After this chapter you will be able to
- Algorithms in everyday software. Explain that algorithms underpin modern computing, including familiar apps and websites, and that their choices affect performance, reliability, and scalability.
- Practical algorithm choice. Justify why a real-world problem does not always call for a clever, complex, or theoretically optimal solution.
- Algorithms Behind Engineering Decisions. Explain why understanding algorithms matters in production work even when programmers rarely implement them from scratch.
- Algorithm Steps and Inputs. Explain that an algorithm solves a well-specified problem through a series of steps that work across a range of inputs and produce an expected output.
- Algorithms and valid solutions. Explain that an algorithm is a set of steps for completing a task or solving a problem, and that a useful solution must work across the intended inputs and give the correct answer within the specified time.
- Efficiency and constraint trade-offs. Explain why different algorithms for the same problem can have different efficiencies and why choosing or optimizing one involves constraints such as time, memory, cost, and scale.
- Efficiency and input growth. Explain why programmers analyze an algorithm's speed and memory use as input changes, and how that analysis helps them compare algorithms or decide whether to improve an implementation.
- Linear search cases. Describe the worst and best cases for the section's linear search example and explain why the section emphasizes the worst case.
- Time and space complexity. Explain that time complexity describes how running time changes with input, while space complexity describes the memory an algorithm needs, and that both matter when choosing an algorithm for large inputs or tight constraints.
- Constant and linear growth. Distinguish O(1) constant time from O(N) linear time using the section's array-access and linear-search examples.
- Logarithmic binary search. Explain why binary search on a sorted array is O(log N): it checks the middle and repeatedly rules out half the remaining array.
- Data structure choice and performance. Explain why choosing a data structure matters even when the algorithm stays the same: the structure affects time complexity, and a poor choice can make a good algorithm too slow at scale.
- Key Value Storage. Explain that a hash map stores unique keys associated with values, and that hashing converts a key into an index used to find its value. Describe how values can be types such as lists, strings, or linked lists.
- Speed and Space Tradeoff. Explain why hash maps can provide near-O(1) insertion, retrieval, and deletion, and why that speed is not guaranteed. Describe the extra memory traded for speed.
- Counting and State Uses. Describe how a hash map can count occurrences by using the item as a key and its frequency as the value. Explain that it can also remember whether something has happened before.
- Linked List Nodes and Traversal. Describe how a linked list stores data in nodes connected by next pointers, and explain why finding an element requires traversal rather than direct access by position.
- Insertion and Deletion Tradeoff. Explain why the section presents insertion and deletion as efficient in linked lists compared with arrays, while distinguishing that advantage from the cost of reaching an element.
- Doubly Linked List Tradeoff. Distinguish a doubly linked list from a singly linked list by its previous pointer, and explain the navigation benefit and memory cost.
- Stack and queue ordering. Distinguish a stack’s last-in, first-out order from a queue’s first-in, first-out order, and identify which element comes out first in each.
- Tree hierarchy and nodes. Explain how a tree organizes data from one root through parent-child relationships to leaf nodes, without loops or nodes having two parents.
- DFS and BFS search order. Distinguish how depth-first search follows a path and backtracks from how breadth-first search checks successive layers.
- Traversal tracking structures. Explain why DFS uses a stack and BFS uses a queue to track which tree nodes to visit, rather than pushing or popping the tree itself.
- Graphs Beyond Tree Hierarchies. Explain why a graph can model connections that a tree hierarchy cannot, and describe the relationship between trees and graphs.
- Cycle Safe Graph Traversal. Describe how DFS and BFS traverse a graph with cycles and why each needs a visited set.
- Matrix And List Representations. Distinguish how an adjacency matrix and an adjacency list record graph connections.
- Directed And Undirected Edges. Distinguish directed from undirected graph connections in adjacency lists and traversal.
Section by section
Introduction
This introduction explains why algorithms matter in everyday software and why choosing one requires practical judgment, not just a search for theoretical optimality.
- Algorithms in everyday software: Explain that algorithms underpin modern computing, including familiar apps and websites, and that their choices affect performance, reliability, and scalability.
Why it matters: Algorithms matter even when users never notice them directly. - Practical algorithm choice: Justify why a real-world problem does not always call for a clever, complex, or theoretically optimal solution.
Why it matters: A solution must work correctly and remain manageable, not merely look impressive on paper.
Key terms: algorithms, performance, reliability, scalability, maintainability, correctness, theoretical optimality
1.1 Setting the Scene
This section explains why working programmers study algorithms even when libraries provide the implementations: to make sound engineering decisions and diagnose performance problems.
- Algorithms Behind Engineering Decisions: Explain why understanding algorithms matters in production work even when programmers rarely implement them from scratch.
Why it matters: Understanding the algorithm beneath a tool helps you decide when to use it and investigate why it struggles.
Key terms: algorithmic trade-offs, scalable architecture, systemic bottlenecks
1.2 Basics of Algorithms
This section defines algorithms as generalizable steps for well-specified problems and introduces how different algorithms can solve the same problem.
- Algorithm Steps and Inputs: Explain that an algorithm solves a well-specified problem through a series of steps that work across a range of inputs and produce an expected output.
Why it matters: This gives you a way to recognize what counts as an algorithm before comparing particular ones. - Different Routes to One Output: Describe how different algorithms can solve the same problem and produce the same output while taking different steps, as illustrated by sorting.
Why it matters: It separates the result an algorithm produces from the steps it uses to get there. - Qualities of Good Algorithms: State the qualities the section gives for a good algorithm: correctness, easy verifiability, and easy implementation.
Why it matters: These are the initial qualities the section offers for judging an algorithm, beyond whether it has steps.
Key terms: algorithms, steps, inputs, expected output, insertion sort, bubble sort, selection sort, correctness, easy verifiability, easy implementation
1.2.1 Algorithms and why do we need them?
This section defines algorithms as problem-solving steps and explains why correctness, input coverage, constraints, and efficiency matter when choosing a solution.
- Algorithms and valid solutions: Explain that an algorithm is a set of steps for completing a task or solving a problem, and that a useful solution must work across the intended inputs and give the correct answer within the specified time.
Why it matters: These are the basic requirements for judging whether a proposed algorithm solves the problem. - Efficiency and constraint trade-offs: Explain why different algorithms for the same problem can have different efficiencies and why choosing or optimizing one involves constraints such as time, memory, cost, and scale.
Why it matters: A correct algorithm is not automatically the best fit for a problem’s practical constraints. - Brute force before optimization: Describe the section’s suggested starting point for solving a problem: first devise a brute-force solution, then work on making it more efficient and fast.
Why it matters: Starting with a straightforward solution gives you something to improve.
Key terms: algorithm, inputs, correct answer, efficiency, time, memory, cost, scale, trade-off, brute force
1.3 Analysis of Algorithms
The section introduces algorithm analysis through efficiency, input size, and the best and worst cases of linear search.
- Efficiency and input growth: Explain why programmers analyze an algorithm's speed and memory use as input changes, and how that analysis helps them compare algorithms or decide whether to improve an implementation.
Why it matters: Considering input growth helps you choose an appropriate algorithm instead of judging code only by how clean it looks. - Linear search cases: Describe the worst and best cases for the section's linear search example and explain why the section emphasizes the worst case.
Why it matters: The search example makes best- and worst-case analysis concrete. - Bounds and notation: State how the section relates worst and best cases to upper and lower bounds, and name the notations it introduces.
Why it matters: These names give you the vocabulary the book uses for discussing algorithmic bounds.
Key terms: efficiency, input, memory, order of growth, linear search, worst-case analysis, best case, N, upper bound, lower bound
1.3.1 Time and Space Complexity
This section introduces time and space complexity and uses familiar search and sorting examples to show how resource use changes as input grows.
- Time and space complexity: Explain that time complexity describes how running time changes with input, while space complexity describes the memory an algorithm needs, and that both matter when choosing an algorithm for large inputs or tight constraints.
Why it matters: Considering memory as well as speed helps you choose an algorithm that fits the problem's constraints. - Constant and linear growth: Distinguish O(1) constant time from O(N) linear time using the section's array-access and linear-search examples.
Why it matters: These examples make the difference between input-independent work and work that grows with input length concrete. - Quadratic and steeper growth: Describe O(N²) growth through the section's nested-loop sorting example, and identify cubic and exponential time as other, inefficient growth categories it mentions.
Why it matters: Recognizing rapidly growing work helps explain why an approach may become impractical on larger inputs. - Logarithmic binary search: Explain why binary search on a sorted array is O(log N): it checks the middle and repeatedly rules out half the remaining array.
Why it matters: Discarding half the candidates at each step explains why binary search scales differently from checking elements one by one.
Key terms: time complexity, space complexity, input, additional data structures, constant time, O(1), linear time, O(N), linear search, N
1.4 Data Structures
This section explains why an algorithm’s performance depends on the data structure used to hold its data.
- Data structure choice and performance: Explain why choosing a data structure matters even when the algorithm stays the same: the structure affects time complexity, and a poor choice can make a good algorithm too slow at scale.
Why it matters: Choosing how to store data can determine whether an otherwise good algorithm remains practical as the workload grows.
Key terms: data structures, time complexity, algorithms
1.4.1 Hash Maps
This section explains how hash maps use keys for fast access, where they are useful, and the tradeoffs that limit their use.
- Key Value Storage: Explain that a hash map stores unique keys associated with values, and that hashing converts a key into an index used to find its value. Describe how values can be types such as lists, strings, or linked lists.
Why it matters: The key-to-index idea explains how a hash map finds a value without searching through every entry. - Speed and Space Tradeoff: Explain why hash maps can provide near-O(1) insertion, retrieval, and deletion, and why that speed is not guaranteed. Describe the extra memory traded for speed.
Why it matters: It helps you judge both the speed benefit and the costs of choosing a hash map. - Counting and State Uses: Describe how a hash map can count occurrences by using the item as a key and its frequency as the value. Explain that it can also remember whether something has happened before.
Why it matters: These are common situations where looking up or updating information by key is useful. - Order Dependent Limitations: Explain why a hash map is not the right structure when a task depends on order or position, such as sorting, traversal, or ranges.
Why it matters: Fast access by key does not make a hash map suitable for every kind of access.
Key terms: hash map, key–value pairs, hash function, index, O(1), O(N), hash collisions, buckets, space complexity, key
1.4.2 Linked List and Doubly Linked List
This section explains how linked and doubly linked lists organize nodes and why their traversal, modification, and memory tradeoffs differ from arrays.
- Linked List Nodes and Traversal: Describe how a linked list stores data in nodes connected by next pointers, and explain why finding an element requires traversal rather than direct access by position.
Why it matters: The node-and-pointer structure explains why linked lists cannot provide array-style access by position. - Insertion and Deletion Tradeoff: Explain why the section presents insertion and deletion as efficient in linked lists compared with arrays, while distinguishing that advantage from the cost of reaching an element.
Why it matters: This distinction helps you choose a structure for the operations a problem actually requires. - Doubly Linked List Tradeoff: Distinguish a doubly linked list from a singly linked list by its previous pointer, and explain the navigation benefit and memory cost.
Why it matters: The extra pointer is useful when backward navigation matters, but it is not free.
Key terms: linked list, node, data, next pointer, traversal, O(N), insertions, deletions, pointers, arrays
1.4.3 Stacks and Queues
The section explains how stacks and queues differ in removal order, where stacks are useful, and how their basic operations are implemented and analyzed.
- Stack and queue ordering: Distinguish a stack’s last-in, first-out order from a queue’s first-in, first-out order, and identify which element comes out first in each.
Why it matters: The removal rule determines which structure fits a task. - Function calls on stacks: Explain how a stack supports function calls: a call adds its local variables and parameters, and finishing the call removes it so control returns to its caller.
Why it matters: Function calls show why the stack’s restrictive removal order is useful. - Basic operations and costs: State the push, pop, and peek operations named for stacks and queues, and describe the time and space costs given in the section.
Why it matters: The costs show that restricting where items are removed can make basic operations efficient. - List and deque implementations: Describe the Python storage choices identified for the example classes: a list for the stack and a collections deque for the queue.
Why it matters: The examples connect the abstract structures to Python storage choices.
Key terms: stack, queue, Last In, First Out (LIFO), First In First out (FIFO), function call, recursion, pushed, pops off, push, pop
1.4.4 Trees
This section introduces tree structure and binary-tree variants, then explains how depth-first and breadth-first traversal work and what they cost.
- Tree hierarchy and nodes: Explain how a tree organizes data from one root through parent-child relationships to leaf nodes, without loops or nodes having two parents.
Why it matters: The hierarchy gives you the vocabulary needed to describe and search a tree. - Binary tree structural variants: Distinguish a binary tree, a full binary tree, and a perfect binary tree by their rules for children and leaf depth.
Why it matters: These names specify different structural constraints, not interchangeable kinds of tree. - DFS and BFS search order: Distinguish how depth-first search follows a path and backtracks from how breadth-first search checks successive layers.
Why it matters: The order of exploration is the central difference between these two ways of searching a tree. - Traversal tracking structures: Explain why DFS uses a stack and BFS uses a queue to track which tree nodes to visit, rather than pushing or popping the tree itself.
Why it matters: The stack or queue turns a search order into a way to keep track of the next node. - Traversal time and space: State the worst-case time cost of both traversals and distinguish their space costs using the tree's maximum width and depth.
Why it matters: The traversals share a worst-case time bound but can need different amounts of tracking space.
Key terms: tree, root, parent, child, leaf node, node, binary tree, full binary tree, perfect binary tree, left
1.4.5 Graphs
Introduces graphs as structures for interconnected networks and explains how to represent, traverse, and analyze them.
- Graphs Beyond Tree Hierarchies: Explain why a graph can model connections that a tree hierarchy cannot, and describe the relationship between trees and graphs.
Why it matters: This distinction tells you when a hierarchy is too restrictive to model a network. - Cycle Safe Graph Traversal: Describe how DFS and BFS traverse a graph with cycles and why each needs a visited set.
Why it matters: The visited set lets familiar traversal methods work without repeatedly circling through a network. - Problem Chosen Source Node: Explain how a traversal's starting node is chosen when a graph has no root.
Why it matters: Choosing a source gives a traversal a meaningful starting point even without a root. - Matrix And List Representations: Distinguish how an adjacency matrix and an adjacency list record graph connections.
Why it matters: These are two concrete ways to store a network's connections in code. - Directed And Undirected Edges: Distinguish directed from undirected graph connections in adjacency lists and traversal.
Why it matters: Edge direction determines both what connections you store and where a search can go. - Graph Traversal Complexity: State the time and visited-set space complexities given for graph BFS and DFS, including what V and E count.
Why it matters: The bounds connect traversal cost to the size of the network and the nodes being tracked.
Key terms: graph, tree, cycle, node, Depth-First Search (DFS), Breadth-First Search (BFS), Visited Set, Queue, source node, starting node
1.5 Summary
Where this is used later
- Understanding the bias and complexity analysis (chapter 2) · Provides the time-and-space analysis vocabulary used when discussing matching complexity.
- All-pairs shortest path (APSP) (chapter 9) · Provides the graph model used for paths between vertices.
- Key Insights (chapter 3) · basic graph terminology
- (chapter intro) (chapter 8) · The idea of routes through a graph.
- Optimization inspired by biology (chapter 8) · Provides the graph vocabulary of nodes and paths.
- What is a clique? (chapter 11) · Provides background for navigating connections among graph vertices.
Concepts explained in this chapter
- space complexityA measure of how an algorithm's memory usage grows as a function of input size.
- time complexityA measure of how an algorithm's running time grows with input size.
- algorithmAn algorithm is a finite step-by-step procedure that transforms specified inputs into a solution to a problem.
- constant timeA time complexity, denoted O(1), that remains bounded independently of input size.
- linear time complexityAn asymptotic linear-time bound in an input of size N, also written O(m) when that input's size is denoted m.
- queueA queue is a first-in-first-out data structure that adds elements at one end and removes them at the other.
- stackA stack is a last-in-first-out data structure that adds and removes elements at one end.
- traversalTraversal is the process of visiting the elements of a data structure in sequence to locate or process them.
- breadth-first searchBreadth-first search is a graph or tree traversal algorithm that explores vertices level by level from a starting vertex.
- doubly linked listA doubly linked list is a linked list whose nodes contain pointers to both the previous and next nodes.
- adjacency listAn adjacency list is a graph representation that stores each vertex together with a collection of its neighboring vertices.
- adjacency matrixAn adjacency matrix is a two-dimensional array whose entries indicate whether pairs of graph vertices are connected.
- directed graphA directed graph is a graph whose edges have a specific orientation from a source vertex to a destination vertex.
- graphA graph is a data structure consisting of vertices and edges that represent entities and relationships.
- undirected graphAn undirected graph is a graph whose edges represent mutual connections without orientation.
- visited setA visited set is a collection of graph vertices already encountered during traversal.
- nodeA node is an element of a linked structure that stores data and one or more links to other nodes.
- first-in-last-out structureLIFO is an ordering rule in which the most recently added element is the first one removed.
- binary treeA binary tree is a tree in which each parent node has at most two child nodes.
- depth-first searchDepth-first search traverses a tree or graph by exploring a path as deeply as possible before backtracking to another branch.
- full binary treeA full binary tree is a binary tree in which every node has either zero children or exactly two children.
- perfect binary treeA perfect binary tree is a binary tree whose internal nodes have two children and whose leaves all occur at the same depth.
- treeA tree is a hierarchical data structure in which every node descends from a single root and edges flow downward without loops.
- scalabilityThe ability of a software system or algorithm to maintain acceptable behavior as workload or resource demands increase.
- tradeoffA trade-off is a situation in which improving one property of a solution requires accepting a reduction in another property.
- linked listA linked list is a sequence of elements connected by links or references to other elements.
- logarithmic time complexityLogarithmic time is a complexity class whose execution time grows in proportion to the logarithm of input size.
- quadratic time complexityA time complexity that grows quadratically with input size, or proportionally to n × m for two input lengths in the stated case.
- correctnessThe property of producing results that satisfy the specified requirements for all applicable inputs and conditions.
- cycleA closed path in a graph that returns to its starting vertex.
- source nodeA source node is the vertex from which a graph traversal or route computation begins.
- worst/best-case analysisWorst-case analysis evaluates an algorithm using the maximum resource cost or execution time over inputs of a given size.
- hash functionA hash function deterministically maps input data, such as a key, to an index or hash value.
- push operationA flow push sends excess flow to a neighboring vertex with residual capacity whose height is exactly one unit lower.
- lower boundA lower bound is a limit that a quantity does not asymptotically fall below.
- dynamic programmingAn algorithm-design technique that solves overlapping subproblems and stores intermediate results to avoid repeated computation.
- brute-force searchBrute force is a problem-solving technique that straightforwardly examines possible solutions without applying problem-specific optimization.
- leaf nodeA leaf node is a tree node with no children.
- root nodeA root node is the single topmost node of a tree from which every other node descends.
- arrayAn array is an indexed collection of elements stored in an ordered sequence.
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.
