CUHKSZ CSC Notes

L0 Introduction

Main Course Topics

• Key algorithm concepts (asymptotic complexity, divide-and-conquer)
• Basic data structure algorithms
  • Heaps (priority queues)
  • Binary seach trees (scheduling)
  • Hashing (cryptography, dictionaries)
• Graph searches (reachability analysis)
• Shortest paths (Google maps, navigation)
• Greedy algorithms (minimum spanning trees, Huffman codes)
• Dynamic programming (any optimization problem)
• Network flows
• Compleity (NP-complete, poly reductions, approximation algorithms)

Textbook: Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani.

L1 Basic Concepts of Algorithmic Performance

Asymptotic Complexity

What is $T(n)$?

$T(n)$ is the largest (worst) execution time over all inputs of size $n$.

Asymptotic Complexity

Goal: Capture the growthm of $T(n)$ of an algorithm as the problem instance size $n \rightarrow \infty$

Key Idea: Keep only the rate of growth, i.e., the dominant term when $n \rightarrow \infty$, forgetting multiplicative constants and lower order terms.

Three Os

1. $\Theta$: Grows asymptotically as fast as ($=$)

   • Tight Bound
   • $f(n) = \Theta(g(n)) \Leftrightarrow \exists c_1, c_2 > 0, n_0 \text{ s.t. } c_1 g(n) \leq f(n) \leq c_2 g(n) \text{ for } n \geq n_0$
   • e.g. $100n^2 + 5n - 5 = 0.1n^2 + 10n^{1.5} - 5 = \Theta(n^2)$

2. $O$: Grows asymptotically at most as fast as ($\leq$)

   • Upper Bound
   • $f(n) = O(g(n)) \Leftrightarrow \exists c > 0, n_0 \text{ s.t. } f(n) \leq c g(n) \text{ for } n \geq n_0$
   • e.g. $2n^{1.5}-5 \leq n^{1.5} \leq n^2 \Rightarrow 2n^{1.5}-5 = O(n^{1.5}), = O(n^2)$
   • e.g. $n^{1.5} \leq n^2 \leq 2^n \Rightarrow n^{1.5} = O(n^2), n^2 = O(2^n), n^{1.5} = O(2^n)$

3. $\Omega$: Grows asymptotically at least as fast as ($\geq$)

   • Lower Bound
   • $f(n) = \Omega(g(n)) \Leftrightarrow \exists c > 0, n_0 \text{ s.t. } f(n) \geq c g(n) \text{ for } n \geq n_0$
   • e.g. $5 \leq 2n \leq n^{1.5}+1 \leq 2^n \Rightarrow 2n = \Omega(1), 2^n = \Omega(n^{1.5})$

In Practice

Conclusions

• To measure the performance of algorithms we measure their asymptotic complexity.
• Big $O$ is used to describe an upper bound for the running time of an algorithm.
• Big $\Omega$ is used to describe a lower bound for the running time of an algorithm.
• Big $\Theta$ is used to denote asymptotic equivalence of the running times of two algorithms. And when $\Omega(g(n)) = O(g(n)) = f(n)$, we can have $\Theta(g(n)) = f(n)$

Divide and Conquer (Sorting and Master Theorem)

Devide and Conquer

There are 3 steps:

1. Divide input into multiple smaller (usually disjoint) points.
2. Conquer each of the parts separatelly (using recursive calls).
3. Combine results from different calls.

$$ T(n) = \text{divide time} \\ +T(n_1) + T(n_2) + \cdots + T(n_k) \\ +\text{combine time} $$

Sorting

A non-D&C solution: Insertion Sort

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

We have the complexity is $O(n^2)$ since it runs two loops with $n$ steps.

But $O(n^2)$ is too slow for most of the problem, can it be much faster? Of course. We can use divide and conquer here!

A D&C solution: Merge Sort

void merge(vector<int>& arr, int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) arr[k++] = L[i++];
        else arr[k++] = R[j++];
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

void mergeSort(vector<int>& arr, int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

From the function mergeSort we can see that we divide the array into $2$ parts and conquer them seperately and recursively. And the merge function has the time complexity of $\Theta(n)$.

From the graph we can see that there is only $\log n$ levels of recursion. Thus, we have

$$ \begin{align} T(n) &= 2T(n/2) + cn \\ &= (cn) \log n + nT(1) \\ &= \Theta (n \log n) \end{align} $$

Where $cn$ denotes for the time of divide and merge, and $T(1)$ represents for the node of the recursion tree.

Geometric Sums

Consider a geometric series $$ S = 1 + x + x^2 + \cdots + x^h = \frac{x^{x+1}-1}{x-1} \ \ (\text{for } x \not= 1) $$ If $x < 1$, then $$ 1 + x + x^2 + \cdots + x^h \in \left[ 1, \frac{1}{1-x} \right] \Rightarrow S = \Theta(1) $$ If $x > 1$ , then $$ 1 + x + x^2 + \cdots + x^h < \frac{1}{1-x} x^h \Rightarrow S = \Theta(x^h) $$