How deeply does Advanced Algorithms and Data Structures cover recurrence?

Defines recurrences, identifies base cases, and solves a factorial example, but defers broader solution techniques to an appendix.

Recurrence

As explained in Advanced Algorithms and Data Structures

A recurrence relation is an equation that defines a sequence or function in terms of values for preceding or smaller instances.

A recurrence relation defines a sequence or function from preceding or smaller instances. In recursive algorithm analysis, it expresses how a problem's running time grows as recursive calls generate smaller inputs. section 15.2.4

Analyze a recursive algorithm by identifying:

The recursive branching pattern, such as calls over every remaining vertex and edge. section 15.2.4
The base case, which determines the recurrence's initial value. section 15.2.4
The resulting growth rate and whether repeated subproblems make the algorithm impractical. section 15.2.4

Factorial growth

For T(n) = n · T(n−1) with T(0) = 1, the solution is T(n) = n!. A recursive graph algorithm with vertex and edge branching grows even faster, restricting it to small graphs. section 15.2.4

T(n,m) = n * T(n-1, m) + m * T(n, m-1)
T(0,0) = 1
T(0,*)=1
T(*,0)=1

Inspect the two-variable recurrence and its boundary conditions for a graph algorithm that removes vertices or edges recursively. section 15.2.4

How Advanced Algorithms and Data Structures covers it

Cover of Advanced Algorithms and Data Structures

liveBook manning.com

Read Advanced Algorithms and Data Structures on liveBook Get the book at manning.com

Also explained in

liveBook manning.com

Natural Language Processing in Action, Second EditionA recurrence loop is a computation pattern that repeatedly feeds a step's state or output into the next step of sequence processing.
liveBook manning.com

Sutskever's ListRecurrence is an architectural mechanism that performs repeated state or representation updates across sequential or iterative computation steps.

Compare how 3 books explain recurrence →

Related concepts

transformer architecturecontrasts with · A transformer architecture is a neural-network architecture that processes sequences or other structured inputs using attention mechanisms and related transformations.
base caseconfigured by · A base case is a condition in a recursive or inductive computation that can be solved directly without further expansion.
recurrent neural networkuses · A recurrent neural network is a neural network that processes sequences by updating an internal state across successive inputs, allowing earlier inputs to influence later computations.
dynamic programmingused by · Dynamic programming is an algorithmic technique that solves problems by decomposing them into overlapping subproblems and storing or reusing their solutions.
knapsack problemuses · The knapsack problem is an optimization problem that selects items subject to a capacity constraint to maximize their combined value.

This explainer was generated by Manning's knowledge graph from the text of Advanced Algorithms and Data Structures. The section links point to the parts of the book it draws on.