brain

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

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

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

Divide-and-conquer algorithms naturally create independent subproblems.

Quickselect finds the \(k\)-th smallest element in expected linear time.

Karatsuba's algorithm demonstrates that multiplication can be accelerated by reducing the number of recursive subproblems.

You need to sort a collection of elements efficiently while preserving the relative order of equal values.

Merge sort guarantees \(O(n \log n)\) performance and stable ordering, but it requires additional memory proportional to the input size.

Many dynamic programming algorithms compute a table with the recurrence: \[ dp[i] = \min_{j < i} \left(dp[j] + cost(j,i)\right) \]

You are given a recursive algorithm and want to determine its time complexity.

You have a divide-and-conquer algorithm and need to analyze its running time and memory usage.

Many divide-and-conquer algorithms produce recurrences of the form \[ T(n)=aT\left(\frac{n}{b}\right)+f(n) \]

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

You have learned the mechanics of divide and conquer: ```text split solve recursively

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

An algorithm can have good asymptotic complexity and still run poorly on real hardware.

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

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

You need to compute: \[ x^n \]

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

You need to answer many queries over a fixed dataset.

You need to multiply two polynomials.

Given \(n\) points on a two-dimensional plane, find the pair of points whose Euclidean distance is minimal.

Interval scheduling is one of the most important greedy problems.

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

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

Scheduling problems occupy a special place in algorithm design.

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

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

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

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

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

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

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

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

Many of the most successful graph algorithms are greedy algorithms.

Many greedy algorithms appear different on the surface.

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

Greedy algorithms often have simple control flow.

Many greedy algorithms appear unrelated on the surface.

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

Greedy algorithms are attractive because they make local decisions.

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

Many greedy algorithms begin with a sort.

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

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

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

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

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

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

State design is the most important step in dynamic programming.

A dynamic programming solution is easy to mistrust.

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

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

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

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

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

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

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

Many dynamic programming solutions are correct but too slow.

The knapsack problem occupies a special place in dynamic programming.

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

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

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

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

Memoization evaluates states on demand through recursion.

Dynamic programming algorithms are especially prone to subtle bugs.

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

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

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

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...

Probability dynamic programming appears when each transition has uncertainty.

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.

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

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

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

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

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

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

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

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

The algorithms developed so far share a common strategy.

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

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

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.

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

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

Scheduling problems often look different from flow problems.

Many optimization problems appear completely different on the surface.

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

You have a set of possible projects.

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

A maximum-flow algorithm returns a number.

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

Edge-disjoint paths are allowed to share vertices.

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

You need to solve an assignment problem exactly.

Standard flow networks place capacity constraints on edges.

Minimum spanning tree algorithms are easy to state, but their performance depends heavily on representation and data structure choices.