brain

You need to measure how far an array is from being sorted.

After studying many divide-and-conquer algorithms, they can appear unrelated.

Divide-and-conquer algorithms naturally create independent subproblems.

You need to find the \(k\)-th smallest element in an unsorted array.

Some problems ask for an optimal value rather than a specific object.

Divide-and-conquer algorithms are prone to subtle implementation errors.

You have learned the main divide-and-conquer patterns in this chapter.

You need to multiply two polynomials.

Given \(n\) points in a plane, find the pair with the smallest Euclidean distance.

A divide-and-conquer algorithm may look correct because its structure is simple: ```text split solve recursively

Many greedy algorithms appear different on the surface.

Many greedy algorithms begin with a sort.

The fractional knapsack problem is one of the clearest examples of a greedy algorithm producing an optimal solution.

Designing a greedy algorithm is often easier than proving it correct.

Interval scheduling is one of the most important greedy problems.

The activity selection problem is historically one of the first optimization problems used to demonstrate the power of greedy algorithms.

Greedy algorithms often have simple control flow.

Many greedy algorithms operate on sorted data and repeatedly make decisions from the extremes of a range.

Greedy algorithms are best learned by proving, breaking, and implementing them.

Greedy algorithms become easier to recognize after seeing them embedded in complete problems.

Greedy algorithms are attractive because they make local decisions.

Many scheduling problems ask a simple question: > Given limited time and many competing jobs, which jobs should be performed?

Many of the most successful graph algorithms are greedy algorithms.

String problems often invite dynamic programming, tries, automata, and hashing.

The classical greedy algorithms presented earlier in this chapter are often introduced as isolated ideas: - Interval scheduling - Huffman coding - Fractional knapsack

The greedy choice property is the fundamental condition that allows a greedy algorithm to produce an optimal solution.

Throughout this chapter, we have studied a wide variety of greedy algorithms: - Interval scheduling - Activity selection - Huffman coding

Scheduling problems occupy a special place in algorithm design.

Many greedy algorithms operate under a simple principle: > A decision is either feasible or infeasible.

Many greedy algorithms are remembered by their choice rule: - Choose the earliest finishing interval.

Most greedy algorithms are not proved by directly showing that the greedy solution is optimal.

Minimum refueling stops is a greedy scheduling problem disguised as a travel problem.

Huffman coding is one of the most successful greedy algorithms ever developed.

A counterexample is a small input that disproves a proposed algorithm, lemma, or proof idea.

Many greedy algorithms appear unrelated on the surface.

Greedy algorithms are among the most elegant techniques in algorithm design.

Throughout this chapter, we have studied many different forms of dynamic programming: * one-dimensional DP * two-dimensional DP * knapsack DP

One-dimensional dynamic programming models progress along a single axis.

Many dynamic programming problems ask for the best solution: ```text minimum cost maximum value

One of the most common mistakes in dynamic programming is focusing exclusively on time complexity while ignoring memory consumption.

Most dynamic programming problems decompose a problem into prefixes, suffixes, positions, or capacities.

Dynamic programming algorithms are especially prone to subtle bugs.

The knapsack problem occupies a special place in dynamic programming.

After defining a state, the next step is to determine how one state depends on other states.

Dynamic programming is easiest when subproblems form a simple order: left to right, bottom to top, short interval to long interval, child before parent.

State design is the most important step in dynamic programming.

The edit distance problem asks a deceptively simple question: > How different are two strings?

The Longest Common Subsequence (LCS) problem is one of the most influential dynamic programming problems ever studied.

One-dimensional dynamic programming is the simplest and most common form of dynamic programming.

This chapter has treated dynamic programming as a toolkit: state design, recurrence construction, memoization, tabulation, counting, optimization, graph DP, interval DP, tree DP, bitmask DP, and trans...

Many dynamic programming solutions are correct but too slow.

Many dynamic programming problems are defined on linear structures such as arrays, strings, and intervals.

Knuth optimization is a specialized dynamic programming optimization for interval-like recurrences.

The Longest Increasing Subsequence (LIS) problem is one of the most important sequence optimization problems in algorithm design.

Once a state and recurrence have been defined, the most direct way to implement a dynamic programming solution is memoization.

A dynamic programming solution is easy to mistrust.

Many dynamic programming recurrences have the correct state design but suffer from an expensive transition step.

Most dynamic programming problems use states based on positions, intervals, capacities, or tree nodes.

Probability dynamic programming appears when each transition has uncertainty.

Memoization evaluates states on demand through recursion.

Optimization dynamic programming is the form most programmers first associate with DP.

Suppose you have an image and want to separate the foreground from the background.

In maximum bipartite matching, every assignment has the same value.

You need to model the movement of resources through a constrained system.

The algorithms developed so far share a common strategy.

Many optimization problems appear completely different on the surface.

Edge-disjoint paths are allowed to share vertices.

Standard flow networks place capacity constraints on edges.

Edmonds-Karp guarantees polynomial running time, but it still performs only one augmentation per BFS search.

Flow algorithms are easy to implement incorrectly because their state changes over time.

Traditional maximum-flow algorithms answer a single question: > How much flow can be sent from the source to the sink?

Suppose you are designing a communication network between two data centers.

So far, flow networks have had a source and a sink.

Suppose you have already constructed a valid flow in a network.

Suppose you have a set of workers and a set of tasks.

Flow algorithms solve the same abstract problem, but their running times differ sharply.

A maximum-flow algorithm returns a number.

Scheduling problems often look different from flow problems.

You need to solve an assignment problem exactly.

Flow implementations are compact, but bugs are easy to hide.

You need to find a maximum matching in a bipartite graph.

Maximum flow asks how much can be sent from a source to a sink.

Given a flow network with capacities on every edge, determine the maximum amount of flow that can be sent from the source to the sink.

A normal flow edge has only an upper capacity: ```text 0 ≤ f(u, v) ≤ c(u, v) ```

You have a set of possible projects.

The Ford-Fulkerson method provides a simple framework for computing maximum flow, but its performance depends heavily on the choice of augmenting paths.

Sparse graphs reward algorithms that touch only existing edges.

Many real-world optimization problems can be modeled as graphs.

A minimum spanning tree gives the cheapest way to connect all vertices.

Many graph algorithms repeatedly ask the same question: > Do these two vertices already belong to the same connected component?

Given a connected weighted undirected graph, find a spanning tree whose total edge weight is minimum.

Minimum spanning tree code often fails for reasons that are easy to miss in clean textbook examples.

Minimum spanning trees minimize the **total weight** of selected edges.

By this point, you have seen three major minimum spanning tree algorithms: ```text Kruskal Prim

The basic union-find structure can become highly unbalanced.

Minimum spanning tree algorithms are short.

Offline connectivity works well when edges are fixed, or when all updates can be processed in a convenient order.

Minimum spanning tree algorithms are usually described in terms of `V` vertices and `E` edges.

Throughout this chapter, we have studied minimum spanning trees from multiple perspectives: * Graph theory * Greedy algorithms * Union-find

Suppose you are given a graph and thousands or millions of connectivity queries: ```text Are vertices u and v connected?