Chapter 13: Where to go next
The chapter previews brief introductions to additional algorithms and suggests further reading based on the reader’s interests.
After this chapter you will be able to
- Line-based value prediction. Explain how linear regression uses a line fitted to known data points to predict a value, using the house-pricing example. State why it is a useful starting technique when the value being predicted is continuous.
- Inverted index word lookup. Explain how an inverted index maps words to the pages where they appear and how a search engine uses that mapping to return results for a word.
- Signal Components and Frequencies. Explain the section’s smoothie analogy and describe how the Fourier transform separates a song into individual frequencies.
- Parallelism across multiple cores. Explain why making an algorithm faster may require changing it to run across multiple cores, and describe the section’s parallel-quicksort example.
- Coordination and uneven work. Describe how the overhead of dividing and recombining work and an uneven distribution of tasks can limit a parallel algorithm’s speedup.
- Amdahl’s law speedup limit. Explain how Amdahl’s law limits the gain from optimizing or parallelizing only one part of a process, using the sketch-and-painting example.
- Distributed processing for large workloads. Explain why a workload might be distributed across multiple machines instead of run on one machine, using one of the section’s examples.
- Large-set membership tradeoff. Explain why services such as Reddit, Google, and bit.ly need to check whether a new item belongs to a large set, and why a hash table is not an unqualified solution.
- Bloom filter answer guarantees. Explain why a Bloom filter’s answer to whether a URL has been crawled is probably, but not always, correct. Distinguish a possible false positive from an impossible false negative.
- Space versus accuracy tradeoff. Explain why the section proposes a Bloom filter instead of a hash table for some checks, and when that tradeoff is acceptable.
- Approximate unique-item counting. Explain why counting unique items exactly can require substantial storage and how HyperLogLog trades exactness for much lower memory use.
- HTTPS encryption and key problem. Explain how a browser and server use the same secret key to encrypt and decrypt messages, and why simply sending that key to the server would be unsafe.
- Diffie–Hellman shared secret. Trace the section’s visual analogy for Diffie–Hellman key exchange, from private keys and a public pattern to public keys and the matching shared secret.
- Hash sensitivity and similarity. Distinguish the effect of a small string change on a SHA-256 hash from its effect on a Simhash hash, and explain why each behavior can be useful.
- Min heap access and removal. Explain that a min heap is a tree-based structure whose smallest value is at the root, making it available in O(1) time; removing it and putting a new minimum in its place takes O(log n) time.
- Heap-based priority queues. Distinguish a priority queue from a FIFO queue and explain why heaps suit priority queues; state that a max heap has its largest value at the root.
- Objectives and linear constraints. Explain that linear programming maximizes an objective subject to linear constraints, and identify the objective and constraints in the production and election examples.
- Interest-driven continued learning. Describe the author’s advice for continuing to learn after the book: choose something that interests you and dive in, using the book as a foundation.
What it builds on
- Using hash tables for lookups (chapter 5) · Using hash tables for lookups
- Quicksort (chapter 4) · The quicksort algorithm used in the section’s example.
- Performance (chapter 5) · The average-case performance of hash tables.
- Hash functions (chapter 5) · The general idea of passing an input through a function.
- Your first tree (chapter 7) · The idea of a tree-based data structure.
- Queues (chapter 6) · A queue returns items in first-in, first-out order.
- Breadth-first search (chapter 6) · Earlier discussion of graph algorithms provides the examples being related to linear programming.
Section by section
Introduction
The chapter previews brief introductions to additional algorithms and suggests further reading based on the reader’s interests.
13.1 Linear regression
The section introduces linear regression as fitting a line to data points and using it to predict a continuous value.
- Line-based value prediction: Explain how linear regression uses a line fitted to known data points to predict a value, using the house-pricing example. State why it is a useful starting technique when the value being predicted is continuous.
Why it matters: A fitted line gives you a simple starting point for predicting a number from observed examples.
Key terms: linear regression, continuous
13.2 Inverted indexes
Introduces inverted indexes as a way to find which pages contain a searched word.
- Inverted index word lookup: Explain how an inverted index maps words to the pages where they appear and how a search engine uses that mapping to return results for a word.
Why it matters: It shows how a search engine can find pages containing a word through a lookup.
Key terms: hash table, inverted index, keys, values
13.3 The Fourier transform
The section introduces the Fourier transform as a way to separate a signal into components and illustrates why that is useful.
- Signal Components and Frequencies: Explain the section’s smoothie analogy and describe how the Fourier transform separates a song into individual frequencies.
Why it matters: Thinking in terms of components makes the section’s examples of processing and compression easier to follow. - Signal Processing and Compression: Describe how separating a signal into components can help adjust music or compress it, and identify the section’s example of another compressed digital signal.
Why it matters: These examples show why separating a signal into components is useful beyond simply describing it.
Key terms: Fourier transform, frequencies, bass, treble, MP3, JPG, digital signal
13.4 Parallel algorithms
This section explains why multicore computers make parallel algorithms valuable and why adding cores rarely produces a proportional speedup.
- Parallelism across multiple cores: Explain why making an algorithm faster may require changing it to run across multiple cores, and describe the section’s parallel-quicksort example.
Why it matters: It explains why using available cores can matter more than waiting for a faster computer. - Coordination and uneven work: Describe how the overhead of dividing and recombining work and an uneven distribution of tasks can limit a parallel algorithm’s speedup.
Why it matters: More cores help less when coordinating them takes time or some finish long before others. - Amdahl’s law speedup limit: Explain how Amdahl’s law limits the gain from optimizing or parallelizing only one part of a process, using the sketch-and-painting example.
Why it matters: It helps you choose which part of an algorithm is worth parallelizing.
Key terms: multiple cores, parallel algorithm, quicksort, overhead of managing the parallelism, load balancing, Amdahl’s law, parallelizing
13.5 map/reduce
This section introduces distributed algorithms, including map/reduce, as a way to speed up very large workloads by running them across multiple machines.
- Distributed processing for large workloads: Explain why a workload might be distributed across multiple machines instead of run on one machine, using one of the section’s examples.
Why it matters: It helps you recognize when a workload is large enough to benefit from multiple machines.
Key terms: distributed algorithm, MapReduce, map/reduce
13.6 Bloom filters and HyperLogLog
This section motivates the problem of checking membership in a very large set: hash-table lookups are fast, but storing all the entries can take too much space.
- Large-set membership tradeoff: Explain why services such as Reddit, Google, and bit.ly need to check whether a new item belongs to a large set, and why a hash table is not an unqualified solution.
Why it matters: It explains why a fast lookup alone may not be enough when the set is enormous.
Key terms: set, hash, hash tables, O(1), constant time
13.7 Bloom filters
This section explains how Bloom filters trade exact answers for low space usage when checking whether an item has been seen before.
- Bloom filter answer guarantees: Explain why a Bloom filter’s answer to whether a URL has been crawled is probably, but not always, correct. Distinguish a possible false positive from an impossible false negative.
Why it matters: The direction of possible error determines whether a Bloom filter is suitable for a check. - Space versus accuracy tradeoff: Explain why the section proposes a Bloom filter instead of a hash table for some checks, and when that tradeoff is acceptable.
Why it matters: It explains why a less certain answer can be preferable to an exact lookup.
Key terms: Bloom filters, false positives, false negatives, hash table
13.8 HyperLogLog
This section introduces HyperLogLog as a memory-efficient way to estimate the number of unique items in a large collection.
- Approximate unique-item counting: Explain why counting unique items exactly can require substantial storage and how HyperLogLog trades exactness for much lower memory use.
Why it matters: It shows when an approximate answer can make counting at large scale practical.
Key terms: HyperLogLog, unique elements, approximate answers
13.9 HTTPS and the Diffie–Hellman key exchange
This section explains how HTTPS uses a shared key to encrypt messages, how Diffie–Hellman lets two parties establish that key without sending it, and why fresh keys limit the damage from a compromised key.
- HTTPS encryption and key problem: Explain how a browser and server use the same secret key to encrypt and decrypt messages, and why simply sending that key to the server would be unsafe.
Why it matters: The key-sharing problem explains why HTTPS needs a key exchange. - Diffie–Hellman shared secret: Trace the section’s visual analogy for Diffie–Hellman key exchange, from private keys and a public pattern to public keys and the matching shared secret.
Why it matters: It shows how both sides can obtain the same key without transmitting that key. - TLS and encryption terminology: Distinguish TLS, the older name SSL, and the symmetric-key encryption described in the HTTPS example.
Why it matters: These terms help you recognize what people mean when they discuss HTTPS security. - Ephemeral keys and exposure: Explain what changes in ephemeral Diffie–Hellman and how that limits the effect of a discovered private key.
Why it matters: Fresh keys keep a single compromised private key from exposing messages across multiple connections.
Key terms: HTTPS, client, server, secret key, encryption, Diffie–Hellman key exchange, private key, public pattern, public key, shared secret
13.10 Locality-sensitive hashing
This section contrasts ordinary hashes with Simhash and explains why similarity-preserving hashes help find similar content.
- Hash sensitivity and similarity: Distinguish the effect of a small string change on a SHA-256 hash from its effect on a Simhash hash, and explain why each behavior can be useful.
Why it matters: Whether a hash preserves similarity determines what comparisons it is useful for. - Similar-content detection uses: Describe how comparing Simhash hashes can help identify duplicate or similar content, using an example from the section.
Why it matters: Similarity checks can flag duplicate pages or potentially copied documents.
Key terms: locality insensitive, locality-sensitive hash function, SHA-256, Simhash, duplicates, similar items
13.11 Min heaps and priority queues
This section explains how heaps expose an extreme value quickly, how repeated removal produces a sorted list, and why heaps are useful for priority queues.
- Min heap access and removal: Explain that a min heap is a tree-based structure whose smallest value is at the root, making it available in O(1) time; removing it and putting a new minimum in its place takes O(log n) time.
Why it matters: The root explains what makes a min heap useful and why looking and removing have different costs. - Sorting by repeated minimums: Describe how repeatedly taking the minimum value from a heap and putting the values in order yields a sorted list, leaving the heap empty.
Why it matters: It shows how quick access to the minimum can be used to sort. - Heap-based priority queues: Distinguish a priority queue from a FIFO queue and explain why heaps suit priority queues; state that a max heap has its largest value at the root.
Why it matters: A priority queue returns what matters most next rather than what arrived first.
Key terms: min heap, root, O(1), O(log n), heapsort, minimum value, max heap, priority queue, FIFO, highest priority
13.12 Linear programming
Introduces linear programming as maximizing an objective under linear constraints, illustrates it with two examples, and relates it to graph algorithms.
- Objectives and linear constraints: Explain that linear programming maximizes an objective subject to linear constraints, and identify the objective and constraints in the production and election examples.
Why it matters: Identifying what to maximize and what limits the choices is the starting point for recognizing a linear-programming problem. - Graph problems within linear programming: Describe how the section relates graph algorithms to linear programming.
Why it matters: This connects earlier graph problems to a broader optimization framework without requiring a new graph algorithm. - Simplex algorithm mention: State the limited role the section assigns to the Simplex algorithm.
Why it matters: It gives the reader a name to pursue without implying that this section teaches the algorithm.
Key terms: linear programming, maximize, linear constraints, graph algorithms, Simplex algorithm
13.13 Epilogue
The epilogue encourages readers to use the book’s foundation to keep learning by exploring a topic that interests them.
- Interest-driven continued learning: Describe the author’s advice for continuing to learn after the book: choose something that interests you and dive in, using the book as a foundation.
Why it matters: It gives you a practical way to continue learning beyond the book.
Key terms: solid foundation, dive in
Concepts explained in this chapter
- MapA dictionary is a Python mapping data structure that associates keys with corresponding values.
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.