brain

Balanced search trees achieve logarithmic performance by carefully maintaining structural invariants.

A randomized algorithm can use randomness in several ways.

Most algorithms assume complete knowledge of the input before computation begins.

Many large-scale systems need to compare sets.

Las Vegas algorithms always return correct answers and use randomness to influence resource consumption.

Randomized algorithms rarely stop at computing an expected value.

Randomized quicksort is one of the most successful applications of randomization in algorithm design.

Primal-dual approximation algorithms use linear programming structure to design fast approximate solutions.

Shuffling converts an ordered collection into a uniformly random permutation.

Randomized algorithms span a wide range of techniques.

Hash tables are usually presented as deterministic data structures: compute a hash, reduce it to a table index, and store or retrieve the key.

Streaming algorithms process data one item at a time while using much less memory than the input size.

Theoretical analysis explains why randomized algorithms work.

Set Cover is the canonical greedy approximation problem.

Many optimization problems can be expressed as integer programs.

Randomized algorithms are often easier to design and analyze than deterministic algorithms.

Some optimization problems are easy to state and hard to solve exactly.

Random sampling is one of the most powerful techniques in algorithm design.

HyperLogLog estimates the number of distinct elements in a stream using a small, fixed amount of memory.

Many applications need to find similar items inside very large collections.

A Bloom filter is one of the most widely deployed probabilistic data structures in modern computing.

Randomized algorithms differ from deterministic algorithms because their behavior depends on random choices made during execution.

Throughout this chapter, we have encountered a recurring theme: ```text A small amount of randomness can dramatically simplify

The Sieve of Eratosthenes is the standard algorithm for generating all primes up to a limit.

Many counting problems ask for results modulo a large number.

Prime numbers occupy a central position in number theory.

Primality testing tells us whether a number is prime.

The Chinese Remainder Theorem is a reconstruction tool.

Many algorithms require computing enormous powers modulo an integer.

A linear congruence is the modular analogue of a linear equation.

Number theory algorithms often look fast because their code is short.

Many counting problems involve inclusion-exclusion.

Number-theoretic algorithms often look simple when written with mathematical notation.

Ordinary logarithms answer the question: ```text a^x = b ```

Exponentiation appears constantly in number-theoretic algorithms.

The Euclidean Algorithm is one of the oldest known algorithms and remains one of the most useful.

The Euclidean Algorithm computes the greatest common divisor of two integers.

Throughout this chapter we studied individual algorithms: - Euclidean Algorithm - Modular Arithmetic - Fast Exponentiation

Euler's phi function counts how many numbers in a range are coprime to a given integer.

After working through the algorithms in this chapter, it is useful to step back and assemble them into a practical toolkit.

A Diophantine equation is an equation whose solutions must be integers.

Number-theoretic code is compact, but its edge cases are dense.

Many number-theoretic algorithms become simpler once a number is expressed as a product of primes.

Primitive roots describe generators of modular multiplication.

Divisibility is one of the most fundamental concepts in number theory.

Division is one of the most subtle operations in modular arithmetic.

The Miller-Rabin test is the practical standard for fast primality testing.

Modular arithmetic is the arithmetic of remainders.

Many geometric problems involve detecting interactions among large collections of geometric objects.

Given a set of points in the plane, construct a triangulation that avoids thin, poorly shaped triangles as much as possible.

Given a set of axis-aligned rectangles, compute the total area covered by their union.

You need to search large collections of geometric objects efficiently.

Geometric algorithms often look exact on paper but fail in code because numeric computations are approximate.

Given a polygon and a query point, determine whether the point lies: ```text inside the polygon outside the polygon

Many computational geometry problems use coordinates that are naturally integers: ```text grid maps pixels

Many geometric algorithms are already asymptotically optimal.

After studying individual geometric algorithms, it is tempting to view them as unrelated techniques.

You need a mathematical representation for locations, directions, distances, and geometric relationships.

Given two lines or two line segments, determine whether they intersect and, if they do, compute the intersection point.

Given a collection of half-planes, compute their common intersection.

Individual geometry algorithms are useful, but real systems usually require several of them working together.

Geometric algorithms are easy to test visually and surprisingly easy to get wrong.

Some geometric problems cannot stay entirely in integer arithmetic.

Many geometric algorithms must determine whether three points form a left turn, a right turn, or lie on the same line.

Given a set of points, partition the plane into regions so that every location belongs to the region of its nearest point.

Given a set of points, compute the smallest convex polygon that contains all of them.

After constructing a convex hull, many geometric questions remain: * What is the maximum distance between any two points?

Most real-world geometry software is not built from a single algorithm.

You need to solve geometric problems that can be reduced to one-dimensional intervals.

You need a fast way to group or search geometric objects by location.

Given a set of points in the plane, find the pair with the smallest Euclidean distance.

Geometry code fails in ways that ordinary examples rarely expose.

Given a polygon described by its vertices, compute its area efficiently and accurately.

Many string algorithms repeatedly compare substrings.

After learning dozens of string algorithms, a natural question remains: > What do real systems actually do?

Many string algorithms need to answer the question: > How many characters match between a string prefix and a substring starting at a particular position?

Many string algorithms assume that a string is simply a sequence of characters.

Many string algorithms depend on a precise ordering of strings.

Throughout this chapter, we studied individual string-processing techniques: - Tokenization - Tries - Hashing

This chapter introduced a large collection of string-processing techniques: - Naive matching - KMP - Z Algorithm

String algorithms are easy to implement incorrectly.

Suppose you need to answer questions such as: - Does a substring occur in the text?

You need to find palindromic substrings efficiently.

Suppose you need to answer many substring queries against the same text.

Suppose you need to search for a pattern inside a large text.

Given two strings, find the longest contiguous block of characters that appears in both.

A single pattern search scans one text once.

Suppose you need to search a text for thousands of patterns simultaneously.

In the previous recipe, you built a suffix array and used it to perform efficient substring searches.

Suppose you need to search for many patterns simultaneously.

String algorithms often look deceptively simple.

Most string algorithms operate on characters.

Many strings contain repeated structure.

Most exact matching algorithms process the text from left to right.

The naive exact matching algorithm repeatedly compares the same characters after every mismatch.

Given a text string and a pattern string, determine whether the pattern occurs in the text and, if so, find all positions where the match begins.

Many string algorithms focus on prefixes, suffixes, or arbitrary substrings.

Exact matching assumes that strings must be identical.

Divide-and-conquer algorithms often fail in ways that are difficult to see from the high-level design.

You need to multiply very large integers.