DSA - Chapter 1

Chapter 1. Induction, Recurrence Equations, and Recursive Calls

Mathematical Induction

• Mathematical Induction is a general way to prove that some statement S(n) about the integer n is true for all n $\ge$ n₀. Step 1: Prove the statement s(n) when n has its smallest value, k.; This is called the basis. Step 2: Prove that if S(n₀), …, S(k) are true for some k $\ge$ n₀, then S(k+1) is also true.; This is called induction.

Recurrence Equations

• A mathematical function is recursive if it is defined in terms of itself. e.g., f(n) = f(n-1) + n²

Telescoping

• The value of a recursive function given certain parameter value(s) can be obtained by telescoping until a base case is reached.

Two rules

• Base case; the case for which the value of the function is directly known without resorting to recursion.
• Progress; For the cases that are to be solved recursively, the recursive call must always be to a case that makes progress towards a base case.

Recursive functions

In recursive programming, we use a solution of a smaller problem to solve a larger proglem.

Example 1: Reverse elements in array A

• Base case: If the array is empty, we don’t have to do anything to reverst it. If there is only one element in the array, we don’t need to do anything at all.

• Insights: If we know how to reverse an array of n-2 elements, we know how to reverse an array of n elements.

reverse(A, p, q) {
    if (p >= q) return;
    swap(A[p], A[q]);
    reverse(A, p+1, q-1);
}

Example 2: Generate all the permutations of n characters stored in the array A[1 … n]

• Recursion strategy (progress): The permutations can be divided into n groups. All permutations in the i-th group are ended with the i-th character. Each group can be formed by permuting the other (n-1) characters and then adding the special one at the end.

perm(A, k, n) {
    if (k==1)
        output A[1 ... n]
    else
        for (i=1 to k) do {
            swap(A[i], A[k]);
            perm(A, k-1, n);
            swap(A[i], A[k]);
        }
}

Conclusion

To analyze a recursive algorithm, we perform 2 tasks:

1. Prove its correctness
   • Use Mathematical Induction
2. Estimate its running time
   • Formulate it as a recursive function