Is "backward substitution" and "backtracking" the same thing?

Question

From my limited knowledge, they both are related to solving recurrence relation.

Solving recurrence relation using backward substitution

Solving recurrence relation using backtracking

• Can the terms be used interchangeably?

In terms of algorithm, I found the following:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. wiki

Backward substitution is a procedure of solving a system of linear algebraic equations Ux=y, where U is an upper triangular matrix whose diagonal elements are not equal to zero. The matrix U can be a factor of another matrix A in its decomposition (or factorization) LU, where L is a lower triangular matrix. This decomposition can be obtained by many methods (for example, the Gaussian elimination method with or without pivoting, the Gaussian compact scheme, the Cholesky decomposition, etc.). Here we also should mention the QR decomposition when the matrix A is represented in the form A=QR, where Q is an orthogonal matrix and R is an upper triangular matrix. Since the matrix U is triangular, a procedure of solving a linear system with the matrix U is a modification of the general substitution method and can be written using simple formulas.

A similar procedure of solving a linear system with a lower triangular matrix is called the forward substitution. Note that the backward substitution discussed here can be considered as a part of the backward Gaussian elimination in the Gaussian elimination method for solving linear systems.

There exists a similar method called the backward substitution with normalization. The scheme of this modification is more complex, since a number of special operations are performed to reduce the effect of round-off errors on the results. algowiki

1. Are backward substitution and backtracking the same in terms of recurrence relation?

2. Is backtracking algorithm is the same as the recurrence relation's backtracking?

3. Is backward substitution (same as back substitution?) in recurrence relation the same with backward substitution algorithm?

4. Is backtracking algorithm the same as backward substitution?

5. What are their relations to each other? backtracking (recurrence relation) - backtracking (algorithm) - backward substitution(recurrence relation) - backward substitution(algorithm)

6. Can the terms be used interchangeably?

Answer 1

• Backward substitution is a specific method to solve a particular problem: a linear system of equations;
• Backtracking is a general paradigm to design algorithms to solve constraint problems in which there can be some sense of "partial solution" and in which the potential invalidity of a partial solution can be tested without completing the partial solution to a complete solution.

This should answer your "can the terms be used interchangeably?" questions: no, they can't.

Imagine you are solving a crosswords puzzle. One algorithm would be: for each definition, find the list of possible words; then try every combination of those words and check if that combination solves the puzzle. This is a bruteforce approach and pretty inefficient. A much better approach is to use backtracking: for each definition, find the list of possible words; choose a word for the first definition; choose a word for the second definition; check immediately for any inconsistency between the two chosen words. If they are inconsistent, "backtrack" by choosing a different word for the second definition. If you run out of words for the second definition, "backtrack" even further by choosing a different word for the first definition. Only if they are consistent, move on to the third definition. This is a backtracking algorithm. Backtracking algorithms are often very straightforward to implement using recursion.

Backward substitution is a method to solve a system of linear equations. A system of linear equations is something that looks like:

a x + b y = c
d x + e y = f

As you can see it is a very specific problem. There is no notion of recursion here. Linear equations are often written in matrix form: A X = B; in my example, A = ((a b)(d e)), X = (x y) and B = (c f).

The article you linked mentioned "recurrence" because they had a problem with cascading linear equations; the linear equations are called a "recurrence relation" because they define a sequence, where X1 = A X0, X2 = A X1, X3 = A X2, etc.