Notes for CLRS (Part I - Fundations)

Muḥammad ibn Mūsā al-Khwārizmī or al-Khwarizmi was a Persian polymath from Khwarazm – Wikipedia

According to Knuth, the word “algorithm” is derived from the name “al-Khowârizmî,” a ninth-century Persian mathematician. – CLRS

Correct Algorithm (P.29)

• An algorithm for a computational problem is correct if, for every problem instance provided as input, it halts — finishes its computing in finite time — and outputs the correct solution to the problem instance.
• An incorrect algorithm might not halt at all on some input instances, or it might halt with an incorrect answer.
• Contrary to what you might expect, incorrect algorithms can sometimes be useful, if you can control their error rate.

2.1 - Insertion Sort

INSERTION-SORT(A, n)  // output from small to large
for i = 2 to n  // subarray A[1:i-1] is sorted
    pickup = A[i]
    j = i-1
    // move elements in the subarray to the right
    // making space for inserting the pickup
    while j>0 and A[j] > pickup :
        A[j+1] = A[j]
        j = j-1
    A[j+1] = pickup  // insert the pickup 

• Proof the correctness of insertion sort by Loop Invariant (Mathematical Induction)
• Loop Invariant: A[1:i-1] is sorted
  • i = 2 is true
  • i = k \(\rightarrow\) i = k+1
  • Terminate when i = n (different from MI)

2.2 - Analyzing algorithms

• Random-Access Machine (RAM) model
• In the RAM model each instruction (±*/=…) or data access takes a constant amount of time
• Gray Area in the RAM model
  • Is x^n a constant-time instruction?
  • Generally, \(O(\log n)\) (eq. 31.34 / page 1205)
  • For \(x=2, n\in\mathbb{N}\): x^n == x<<(n-1), \(O(1)\)
  • We just treat all of them as \(O(1)\) in RAM model

2.2 - Analyzing algorithms

• Running time depends on the input
• Input size:
  • number of
    • items(sort)
    • bits(multiplying)
    • vertices/edges (in the graph)
• The running time of an algorithm on a particular input is the number of instructions and data accesses executed. (RAM model)

Analysis of insertion sort

INSERTION-SORT(A, n)              # cost times
for i = 2 to n                    # c1   n
    pickup = A[i]                 # c2   n-1
    j = i-1                       # c3   n-1
    while j>0 and A[j] > pickup : # c4   sum_{i=2}^{n} m_i
        A[j+1] = A[j]             # c5   sum_{i=2}^{n} m_i-1
        j = j-1                   # c6   sum_{i=2}^{n} m_i-1
    A[j+1] = pickup               # c7   n-1

\[ \begin{aligned} T(n) &= c_1 n + [c_2+c_3+c_7] (n-1) \\ &+ c_4 \sum_{i=2}^n m_i + [c_5+c_6] \sum_{i=2}^n (m_i - 1) \end{aligned} \]

• \(m_i\) is the number of times the while loop run +1
• \(m_i=1\) for best case (A is already sorted)
• \(m_i=i\) for worst case (A is reverse ordered)

Analysis of insertion sort (best case)

\[ \begin{aligned} T(n) &= c_1 n + [c_2+c_3+c_7] (n-1) \\ &+ c_4 \sum_{i=2}^n m_i + [c_5+c_6] \sum_{i=2}^n (m_i - 1) \end{aligned} \]

• \(m_i=1\) for best case (A is already sorted)
  \(c_4 \sum_{i=2}^n m_i = c_4 (n-1)\)
  \[ \begin{aligned} T(n) &= c_1 n + [c_2+c_3+c_7+c_4] (n-1) \\ &= a n + b \end{aligned} \]
• \(\Theta(n)\) (Pronounced "theta of n" or "theta n"), i.e., Linear Time

Analysis of insertion sort (worst case)

\[ \begin{aligned} T(n) &= c_1 n + [c_2+c_3+c_7] (n-1) \\ &+ c_4 \sum_{i=2}^n m_i + [c_5+c_6] \sum_{i=2}^n (m_i - 1) \end{aligned} \]

• \(m_i=i\) for worst case (A is reverse ordered)
  \(\sum_{i=2}^n m_i = \frac{(2+n)(n-1)}{2}=\frac{n^2+n-2}{2}\)
  \(\sum_{i=2}^n (m_i-1) = \frac{n^2+n-2}{2}-(n-1)=\frac{n^2-n}{2}\)
  \(T(n)=cn^2+dn+e\)
• \(\Theta(n^2)\) (Pronounced "theta of n-squared" or "theta n-squared"), i.e., Quadratic Time

Due to constant factors and lower-order terms, an algorithm whose running time has a higher order of growth might take less time for small inputs than an algorithm whose running time has a lower order of growth.

2.3 Designing algorithms

• Incremental method: e.g., Insertion Sort
• Divide and Conquer: e.g., Merge Sort

def MergeSort(A, left, right):
if left >= right:  # zero or one element
    return
mid = floor((left+right)/2)
MergeSort(A, left, mid)
MergeSort(A, mid+1, right)
Merge(A, left, mid, right)

3.1 - \(O\), \(\Omega\), and \(\Theta\)-notation

• Suggested by Aho, Hopcroft, and Ullman [1], it becomes prevalent to use \(O\), \(\Omega\), and \(\Theta\)-notation to describe the asymptotic behavior of algorithms.
• They are general notations that can be used for Time Complexity, Space Complexity, …
• \(O(f(n))\) is an asymptotic upper bound
  • e.g., \(5n^3+3n\) is \(O(n^3)\), \(O(n^4)\), \(O(n^5)\),…
• \(\Omega(f(n))\) is an asymptotic lower bound
  • e.g., \(5n^3+3n\) is \(\Omega(n^3)\), \(\Omega(n^2)\), \(\Omega(n)\),…
• \(\Theta(f(n))\) is the asymptotic tight bound
  • e.g., \(5n^3+3n\) is \(\Theta(n^3)\)
• As a result, if you can show a function is both \(O(n^3)\) and \(\Omega(n^3)\), it is, then, must be \(\Theta(n^3)\).

[1] Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.)

Revisit Insertion Sort (step1: \(O(n^2)\))

INSERTION-SORT(A, n)
for i = 2 to n
    pickup = A[i]
    j = i-1
    while j>0 and A[j] > pickup :
        A[j+1] = A[j]             # Line 6 - Move element by one position 
        j = j-1
    A[j+1] = pickup

• The outer for loop runs n-1 times
• The inner while loop might runs 0(best) to i-1(worst) times depending on the input array A
• i<=n
• Number of iterations of the inner loop is therefore at most \((n-1)(n-1)\), which is \(O(n^2)\)

Revisit Insertion Sort (step2: \(\Omega(n^2)\))

INSERTION-SORT(A, n)
for i = 2 to n
    pickup = A[i]
    j = i-1
    while j>0 and A[j] > pickup :
        A[j+1] = A[j]             # Line 6 - Move element by one position 
        j = j-1
    A[j+1] = pickup

• Assume \(n \equiv 0 \pmod 3\), we can devide the A into three pieces: A[1:n/3], A[n/3+1:2n/3], A[2n/3+1:n].
• Assume \(\frac{n}{3}\) numbers in the first piece A[1:n/3] are greater than the rest of the input array A.
• After sorting, all these \(\frac{n}{3}\) numbers must be moved to somewhere in the third piece A[2n/3+1:n] by the Line 6 in the above code.
• Each of these numbers will be moved by at least \(\frac{n}{3}\) times to accross the middle piece A[n/3+1:2n/3].
• So, Line 6 will be executed at least \(\frac{n}{3}\frac{n}{3}=\frac{n^2}{9}\) times.
• For this particular case, it is \(\Omega(n^2)\)

Revisit Insertion Sort (step3: \(\Theta(n^2)\))

INSERTION-SORT(A, n)
for i = 2 to n
    pickup = A[i]
    j = i-1
    while j>0 and A[j] > pickup :
        A[j+1] = A[j]             # Line 6 - Move element by one position 
        j = j-1
    A[j+1] = pickup

• Step1: \(O(n^2)\) in all cases
• Step2: \(\Omega(n^2)\) in a particular case
• Step3: Insertion Sort is \(\Theta(n^2)\) in the worst case.

Remarks (Page 95)

• ✅ Insertion sort's best-case running time is \(O(n)\), \(\Omega(n)\), and \(\Theta(n)\)
• ✅ Insertion sort's worst-case running time is \(O(n^2)\), \(\Omega(n^2)\), and \(\Theta(n^2)\)
• ❌ Insertion sort's running time is \(\Theta(n^2)\)
  • Because in best-case, it is \(\Theta(n)\)
• ✅ Insertion sort's running time is \(O(n^2)\)
• ✅ Insertion sort's running time is \(\Omega(n)\)
• ✅ Merge sort runs in \(\Theta(n \lg n)\) time (in all cases)

Amortized

• Detail discussed in Ch.16
• "In an amortized analysis, you average the time required to perform a sequence of data-structure operations over all the operations performed."
• "Amortized analysis differs from average-case analysis in that probability is not involved. An amortized analysis guarantees the average performance of each operation in the worst case."

Misc.

• Formally, \(f(n) = O(g(n))\) means \(f(n) \in O(g(n))\), where \(O(g(n))\) is a set of functions.
• There are also \(o\) and \(\omega\) notations
  \(f(n) = O(g(n))\) is like \(f \le g\)
  \(f(n) = \Omega(g(n))\) is like \(f \ge g\)
  \(f(n) = \Theta(g(n))\) is like \(f = g\)
  \(f(n) = o(g(n))\) is like \(f < g\)
  \(f(n) = \omega(g(n))\) is like \(f > g\)

3.3 - Standard notations and common functions

• Floor/Ceiling

  • floor(1.7)\(= \lfloor 1.7 \rfloor = 1\)
  • ceil(1.7)\(= \lceil 1.7 \rceil = 2\)
  • \(\lceil x \rceil \ge x \ge \lfloor x \rfloor \quad \forall x \in \mathbb{R}\)

• Modular

  • a%n\(= (a \bmod n) = a - n \lfloor \frac{a}{n}\rfloor\)
  • \((a \bmod n) = (b \bmod n) \Rightarrow a \equiv b \pmod n\)
    i.e., \(a\) is equivalent to \(b\), modulo \(n\)

• \(\lg n = \log_2 n\)

Intro - Divide-and-Conquer

• Base Case: Solve it directly

• Recursive Case: Devide it recursively until reaching the base case (bottoms out). This invloves three steps:

  1. Divide the problem into subproblems
  2. Conquer the subproblems recursively
  3. Combine the subproblems to solve the original problem

Compared to Dynamic Programming (Ch14)

• In contrast to divide-and-conquer, dynamic programming applies when subproblems share subsubproblems.
• A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table for looking up later.

Algorithmic recurrences

• Recurrence \(T(n)\) is algorithmic if, for every sufficiently large threshold constant \(n_0>0\), we have:

  1. \(\forall n<n_0\), we have \(T(n) = \Theta(1)\).
  2. \(\forall n \ge n_0\), all recursion terminates in a defined base case within a finite number of recursive invocations.

• An example of recurrence \(T(n)\):

  • The running time of Strassen’s algorithm can be described by the recurrence: \[T(n) = 7 T(n/2)+\Theta(n^2)\]
  • The solution is \[T(n) = \Theta(n^{\lg 7})\approx\Theta(n^{2.81})\]

4.1 - Multiplying Square Matrices (directly)

def Matrix_Multiply(A, B, C, n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i,j] += A[i,k]*B[k,j]

• \(\Theta(n^3)\) time complexity

4.1 - Multiplying square Matrices (Simple Divide-and-Conquer)

• Assume \(n\) is an exact power of 2.
• Devide original \(n \times n\) matrices (\(A, B, C\)) into \(\frac{n}{2}\times\frac{n}{2}\) ones (\(A_{11}, A_{12}, \ldots\)) and expand the multiplication:
  \[ \begin{align} C &= A \cdot B \\ \Rightarrow \begin{pmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \end{pmatrix} &= \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} \begin{pmatrix} B_{11} & A_{12} \\ B_{21} & A_{22} \end{pmatrix} \\ &= \begin{pmatrix} A_{11} \cdot B_{11} +A_{12} \cdot B_{21} & A_{11} \cdot B_{12} +A_{12} \cdot B_{22} \\ A_{21} \cdot B_{11} +A_{22} \cdot B_{21} & A_{21} \cdot B_{12} +A_{22} \cdot B_{22} \end{pmatrix} \end{align} \]

4.1 - Multiplying square Matrices (Simple Divide-and-Conquer)

def Matrix_Multiply_Recursive(A, B, C, n):
    if n == 1:    # Base Case
        C[1,1] += A[1,1]*B[1,1]
        return
    else:         
        # Divide
        [A11, A12, A21, A22, B11, B12, B21, B22, C11, C12, C21, A22] = Part(A,B,C)
        # Conquer
        Matrix_Multiply_Recursive(A11, B11, C11, n/2)
        Matrix_Multiply_Recursive(A11, B12, C12, n/2)
        Matrix_Multiply_Recursive(A21, B11, C21, n/2)
        Matrix_Multiply_Recursive(A21, B12, C22, n/2)
        Matrix_Multiply_Recursive(A12, B21, C11, n/2)
        Matrix_Multiply_Recursive(A12, B22, C12, n/2)
        Matrix_Multiply_Recursive(A22, B21, C21, n/2)
        Matrix_Multiply_Recursive(A22, B22, C22, n/2)

• \(T(n)=8T(n/2)+\Theta(1)\)
• From the master method in Sec. 4.5, we can show it has the solution: \(T(n) = \Theta(n^3)\)
• Could we make it better than \(\Theta(n^3)\)?

4.2 - Strassen’s algorithm for matrix multiplication

• It is hard to imagine that any matrix multiplication algorithm could take less than \(\Theta(n^3)\) time, since the natural definition of matrix multiplication requires \(n^3\) scalar multiplications. Indeed, many mathematicians presumed that it was not possible to multiply matrices in \(o(n^3)\) time until 1969, when V. Strassen [424] published a remarkable recursive algorithm for multiplying \(n \times n\) matrices

• The running time of Strassen’s algorithm is \(\Theta(n^{\lg 7})\approx\Theta(n^{2.81})\)

• [424] Volker Strassen. Gaussian elimination is not optimal, Numerische Mathematik, 14(3):354–356, 1969.

4.2 - Strassen’s algorithm for matrix multiplication (cont.)

• The basic idea is similar to \(x^2-y^2=(x-y)(x+y)\), where we can turn 2 multiplication and 1 "addition" into 2 "addition" and 1 multiplication.
• For scalar operation, the difference between multiplication and addition is not huge. However, it is a big difference for matrices.
• Instead of deviding the original \(n \times n\) matrix multiplication into 8 matrix multiplication of \(\frac{n}{2}\times\frac{n}{2}\) matrices, Strassen only perform 7 matrix multiplication of \(\frac{n}{2}\times\frac{n}{2}\) matrices with some extra addition (substraction) operations.
• So, the recurrence for the running time of Strassen’s algorithm is \[T(n) = 7T(n/2)+\Theta(n^2)\]
• Link: Wikipedia - Strassen’s Algorithm

4.3 - The substitution method for solving recurrences

4.4 - The recursion-tree method for solving recurrences

4.5 - The master method for solving recurrences

• The master method provides a “cookbook” method for solving algorithmic recurrences of the form: \[T(n) = aT(n/b)+f(n)\]
  • A recurrence of this general form is called master recurrence.
  • \(f(n)\) is the driving function
  • It means we divide a problem of size \(n\) into \(a\) subproblems, each of size \(n/b<n\).