page: https://www.student.cs.uwaterloo.ca/~cs240/s20/

Instructor: Eric Schost, Armin Jamshidpey, Gautam Kamath

• Week 1. May 11
• Week 2. May 18
• Week 3. May 25
• Week 4. June 1
• Week 5. June 9
• Week 6. June 16
• Week 7. June 23
• Week 8. June 29
• Week 9. July 6
• Week 10. July 14
• Week 11. July 21
• Week 12. July 28
• Week 13. August 3

Week 1. May 11

running time simplifications

random access machines model

• the ram has a set of memory cells, each of which stores one item of dara
• any access to a memory location takes constant time
• any primitive operation takes constant time
• the running time of a program = # of memory access + # of primitive operations

defn. (O-notation) $f(n)\in O(g(n))$ if there exist constants $c>0$ and $n_0>0$ such that $|f(n)| \leq c|g(n)|$ for all $n\geq n_0$. (upper bound)

eg. f(n)=75n+500, g(n)=5n^2 (c=1, n0=20). (we ignore smaller inputs)

eg. show $2n^2+3n+11\in O(n^2)$ from first principles.
we need to find $c$ and $n_0$ so that we have $0 \leq 2 n^{2}+3 n+11 \leq c n^{2}, \forall n \geq n_{0}$.
can let $n_0=1$, so $1\leq n\longrightarrow 1\leq n^2\longrightarrow11\leq 11n^2$, $1\leq n\longrightarrow n\leq n^2\longrightarrow 3n\leq 3n^2$, $2n^2\leq 2n^2$. so $2n^2+3n+11\leq 11n^2+3n^2+2n^2=16n^2$, so $c=16$. $\square$

defn. (Omega-notation) $f(n)\in \Omega(g(n))$ if there exist constants $c>0$ and $n_0>0$ such that $0\leq c|g(n)| \leq |f(n)|$ for all $n\geq n_0$. (lower bound)

defn. (Theta-notation) $f(n) \in \Theta(g(n))$ if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$. (tight bound)

eg. show $\frac{1}{2} n^{2}-5 n \in \Omega\left(n^{2}\right)$ from first principles.
let $n_0=20$, have $n\geq 20\longrightarrow n^2\geq 20n\longrightarrow \frac{1}{4}n^2\geq 5n\longrightarrow \frac{1}{4}n^2-5n\geq 0$. so $\frac{1}{2}n^2-5n=\frac{1}{4}n^2+(\frac{1}{4}n^2-5n)\geq \frac{1}{4}n^2$. let $c=\frac{1}{4}$. $\square$

defn. (omega-notation) $f(n) \in o(g(n))$ if for all constants $c>0$, there exists a constant $n_0>0$ such that $|f(n)|<c|g(n)|,\forall n \geq n_{0}$.

defn. (theta-notation) $f(n) \in \omega(g(n))$ if for all constants $c>0$, there exists a constant $n_0>0$ such that $0\leq c|g(n)|<|f(n)|,\forall n \geq n_{0}$.

theorem. $f(n) \in \Theta(g(n)) \Longleftrightarrow g(n) \in \Theta(f(n))$
proof. there exist $n_0,c_1,c_2$ with $c_1|g|\leq|f|\leq c_2|g|,\forall n\geq n_0$, so $\frac{1}{c_2}|f|\leq|g|\leq\frac{1}{c_2}|f|,\forall n\geq n_0$. $\square$

theorem. $f(n) \in O(g(n)) \Longleftrightarrow g(n) \in \Omega(f(n))$

theorem. $f(n) \in o(g(n)) \Longleftrightarrow g(n) \in \omega(f(n))$

theorem. $f(n) \in o(g(n)) \Longrightarrow f(n) \in O(g(n))$

theorem. $f(n) \in o(g(n)) \Longrightarrow f(n) \notin \Omega(g(n)$

theorem. $f(n) \in \omega(g(n)) \Longrightarrow f(n) \in \Omega(g(n))$

theorem. $f(n) \in \omega(g(n)) \Longrightarrow f(n) \notin O(g(n))$

theorem. (identity rule) $f(n) \in \Theta(f(n))$

theorem. (max rules) suppose $f(n)>0$ and $g(n)>0$ for all $n\geq n_0$, then

1. $O(f(n)+g(n))=O(\max \{f(n), g(n)\})$
2. $\Omega(f(n)+g(n))=\Omega(\max \{f(n), g(n)\})$

proof. (1) let $h\in O(f+g)$, then $\exist c, n_0>0$ with $|h|\leq c|f+g|\leq 2c|\max\{f,g\}|,\forall n\geq n_0$ so $h\in O(\max\{f,g\})$. let $h\in O(\max\{f,g\})$, then $\exist c,n_0>0$ with $|h|\geq c|\max\{f,g\}|=\frac{c}{2}|2\max\{f,g\}|\geq\frac{c}{2}|f+g|,\forall n\geq n_0$, so $h\in O(f+g)$. $\square$

theorem. (transitivity)

• if $f(n) \in O(g(n))$ and $g(n) \in O(h(n))$ then $f(n) \in O(h(n))$
• If $f(n) \in \Omega(g(n))$ and $g(n) \in \Omega(h(n))$ then $f(n) \in \Omega(h(n))$

proof. (1) there exist $c_1,n_1>0$ with $|f|\leq c_1|g|,\forall n\geq n_1$, there exist $c_2,n_2$ with $|g|\leq c_2|h|,\forall n\geq n_2$. take $N=\max\{n_1,n_2\}$ we have $|f|\leq n_1n_2|h|,\forall n\geq N$. $\square$

theorem. suppose $f(n)>0$ and $g(n)>0$ for all $n\geq n_0$, suppose $L=\lim _{n \rightarrow \infty} \frac{f(n)}{g(n)}$, then

$f(n) \in\left\{\begin{array}{ll}o(g(n)) & \text { if } L=0 \\ \Theta(g(n)) & \text { if } 0<L<\infty \\ \omega(g(n)) & \text { if } L=\infty\end{array}\right.$

the other side does not hold.

eg. let $f(n)$ be a polynomial $f(n)=c_{d} n^{d}+c_{d-1} n^{d-1}+\cdots+c_{1} n+c_{0}$ for some $c_d>0$, then $f(n) \in \Theta\left(n^{d}\right)$.
proof.

$\begin{aligned} \lim _{n \rightarrow \infty} \frac{f(n)}{n^{d}} &= \lim _{n \rightarrow \infty} \frac{c_{d} n^{d}+c_{d-1} n^{d-1}+\cdots+c_{1} n+c_{0}}{n^{d}}\\ &= \lim_{n\rightarrow\infty}\frac{c_1n^d}{n^d}+\lim_{n\rightarrow\infty}\frac{c_{d-1}n^{d-1}}{n^{d}}+...+\lim_{n\rightarrow\infty}\frac{c_0}{n^d} \\ &= c_d+0+...+0\\ &= c_d >0 \end{aligned}$

use the limit rule we have $f(n) \in \Theta\left(n^{d}\right)$. $\square$

eg. show $n(2+\sin n \pi / 2)$ is $\Theta(n)$.
proof. note $\lim_{n\rightarrow \infty}\frac{n(2+\sin n\frac{\pi}{2})}{n}=\lim_{n\rightarrow\infty}(2+\sin n\frac{\pi}{2})$ does not exist.

note if $n_0=1$, then for all $n\geq n_0$ we have $-1\leq \sin n\frac{\pi}{2}\leq 1$, so add sides by $2$ and times $n$, we have $n\leq n(2+\sin n\frac{\pi}{2})\leq 3n$. $\square$

• if $f(n) \in \Theta(g(n))$, then the growth rates of both functions are the same.
• if $f(n) \in o(g(n))$, then the growth rate of $f(n)$ is less than the growth rate of $g(n)$
• if $f(n) \in \omega(g(n))$, then the growth rate of $f(n)$ is greater than the growth rate of $g(n)$

we write $\log n$ to represent $\log_2n=\frac{\ln n}{\ln 2}$

eg. compare the growth rates of logn and n.
$\lim_{n\rightarrow\infty}\frac{\log n}{n}=\lim_{n\rightarrow\infty}\frac{\frac{1}{n\ln 2}}{1}=\lim_{n\rightarrow\infty}\frac{1}{n\ln 2}=0$, so $\log n\in o(n)$ by LH.

eg. compare the growth rates of $(\log n)^c$ and $n^d$ where $c,d>0$ are arbitrary.
repeatedly apply LH we have $\lim_{n\rightarrow\infty}\frac{(\log n)^c}{n^d}=\lim_{n\rightarrow\infty}\frac{c!}{(\ln 2)^cd^cn^d}=0$ so $(\log n)^c\in o(n^d)$.

common growth rates from best to worse

• $\Theta(1)$: constant complexity (array lookup)
• $\Theta(\log n)$: logarithmic complexity (binary search)
• $\Theta(n)$: linear complexity (search in array)
• $\Theta(n\log n)$: linearithmic (mergesort)
• $\Theta(n\log^k n)$ for some constant $k$: quasi-linear
• $\Theta(n^2)$: quadratic complexity (polynomial multiplication)
• $\Theta(n^3)$: cubic complexity (matrix multiplication)
• $\Theta(2^n)$: exponential complexity

eg. double the size of input for linearithmic algorithm, what's resultant running time?
have $T(n)=cn\log n$, then $T(2n)=c2n\log 2n=2cn(\log n+\log 2)=2cn\log n+2cn=2T(n)+2cn$. not bad

techniques for analysis

• running time depends on the input size n
• identify elementary operations that require $\Theta(1)$ time
• the complexity of a loop is expressed as the sum of the complexities if each iteration of the loop
• nested loops: start with the innermost loop and proceed outwards

eg.

Test1(n):
    auto sum = 0                    // Theta(1) --> c_1
    for i = 1, n:                   // \sum{i=1,n} A
        for j = i, n:               //  \sum{j=i,n} c_2 --> A
            sum = sum + (i-j)^2     //   Theta(1) --> c_2
    return sum                      // Theta(1) --> c_3

method1:

$\begin{aligned} T(n) &= c_1+c_3+\sum_{i=1}^n\sum_{j=i}^nc_2 \\ &= c_0 +\sum_{i=1}^n(\sum_{j=i}^nc_2)\\ &= c_0+\sum_{i=1}^nc_2(n-i+1)\\ &= c_0+\sum_{i=1}^nc_2n-\sum_{i=1}^nc_2i+\sum_{i=1}^nc_2\\ &= c_0+c_2n^2-c_2(\frac{n(n-1)}{2})+c_2n\\ &= c_0+c_2(\frac{2n^2}{2}+\frac{n^2+n}{2}+\frac{2n}{n})\\ &= c_0+c_2(\frac{n^2+n}{2})\\ &= c_0+\frac{c_2}{2}(n^2+n)\in\Theta(n^2) \end{aligned}$

method2:

$\begin{aligned} T(n) &= c_1+c_3+\sum_{i=1}^n\sum_{j=i}^nc_2 \\ &\leq c_0+\sum_{i=1}^n\sum_{j=1}^nc_2\\ &= c_0+c_2\sum_{j=1}^n\sum_{j=1}^n1\\ &= c_0+c_2n^2\in O(n^2)\\ T(n) &= c_1+c_3+\sum_{i=1}^n\sum_{j=i}^nc_2\\ &\geq c_0+\sum_{i=1}^{n/2}\sum_{j=i}^nc_2\\ &\geq c_0+\sum_{i=1}^{n/2}\sum_{j=n/2+1}^nc_2\\ &= c_0+c_2\frac{n}{2}\sum_{i=1}^{n/2}1\\ &= c_0+c_2\frac{n^2}{4}\in\Omega(n^2) \end{aligned}$

eg. show $f(n)=\sum_{i=1}^n\sum_{j=i}^n\sum_{k=j}^i1\in\Theta(n^3)$
$f(n)\leq\sum_{i=1}^n\sum_{j=1}^n\sum_{k=1}^n=n^3\in O(n^3)$
$f(n)\geq\sum_{i=1}^{n/3}\sum_{j=2n/3+1}^n\sum_{k=n/3+1}^{2n/3}=...\in\Omega(n^3)$

Week 2. May 18

The running time may depend on the characteristic of the input

defn. let $T_A(I)$ denote the running time of an algorithm A on instance I of length n,

• best-case complexity take the best I, with shortest time
• worst-case complexity take the worst I, with longest time
• average-case complexity take the average I

we assume the worst-case complexity if not specified.

eg.

Test(A, n):
    for i = 1, n-1:                     //     \sum_{i=1,n-1} M
        auto j = i
        while j > 0 and A[j] > A[j-1]:  //      M (worst: if j A[j] always > A[j-1]
            swap(A[j], A[j-1])          //         need to loop from 0 to i)
            j = j-1                     //

worst case: $\Theta(n^2)$

• it is important not to try and make comparison between algorithms using O-notation
• if A1, A2 solves same problem, A1 has worst O(n^3), A2 has worst O(n^2)
• we cannot conclude A2 is more efficient than A1 for all input
  • the worst-case runtime may only be achieved on some instances
  • O is upper bound. A1 may have O(n).
  • should always use $\Theta$-notation

mergesort

design

1. split A into two subarrays AL consists of the first $\Bigl\lceil\dfrac{n}{2}\Bigr\rceil$ elements and AR consists of the last $\Bigl\lfloor\dfrac{n}{2}\Bigr\rfloor$ elements.
2. recursively call mergesort on AL and AR
3. AL and AR are sorted, merge them into a single sorted array (merge two sorted arrays)

mergesort(A[n], l = 0, r = n-1):
    if r <= l:                // \Theta(1)
        return                  // \Theta(1)
    else:
        auto m = (r+l)/2      // \Theta(1)
        mergesort(A, l, m)    // T(n/2)
        mergesort(A, m+1, r)  // T(n/2)
        merge(A, l, m, r)     // ?

// assume A[l:m], A[m+1:r] are sorted
merge(A[n], l, m, r):
    auto S = // auxiliary array of size n
    auto S[l:r] = A[l:r]  // copy A[l,...,r] to S[l,...,r]
                          // this is step 1, taking \Theta(n)
    int iL = l
    int iR = m+1
    for k = l, r:                // \sum_{k=l,r}
        if iL > m:
            A[k] = S[iR++]
        else if iR > r:
            A[k] = S[iL++]
        else if S[iL] <= S[iR]:
            A[k] = S[iL++]
        else:
            A[k] = S[iR++]

merge takes $\Theta(r-l+1)$, which is $\Theta(n)$ (!)
so the total time for mergesort should be $T(n)=2T(\frac{n}{2})+\Theta(n)$

analysis

let T(n) denote the time to run mergesort on an array of length n

• step 1 takes $\Theta(n)$
• step 2 takes $T(\Bigl\lceil\dfrac{n}{2}\Bigr\rceil)+T(\Bigl\lfloor\dfrac{n}{2}\Bigr\rfloor)$
• step 3 takes $\Theta(n)$

the recurrence relation for T(n) is:

$T(n)=\begin{cases} T(\Bigl\lceil\dfrac{n}{2}\Bigr\rceil)+T(\Bigl\lfloor\dfrac{n}{2}\Bigr\rfloor)+\Theta(n) & \text{ if } n>1 \\ \Theta(1) & \text{ if } n= 1 \end{cases}$

it suffices to consider the exact relation, with constant factor c replacing $\Theta$'s

$T(n)=\begin{cases} T(\Bigl\lceil\dfrac{n}{2}\Bigr\rceil)+T(\Bigl\lfloor\dfrac{n}{2}\Bigr\rfloor)+cn & \text{ if } n>1 \\ c & \text{ if } n= 1 \end{cases}$

the sloppy recurrence (with floors and ceilings removed) is:

$T(n)=\begin{cases} 2T(\frac{n}{2})+cn & \text{ if } n>1 \\ c & \text{ if } n= 1 \end{cases}$

• the exact and sloppy recurrences are identical when n is power of 2

solve with method 1

$\begin{aligned} T(n) &= 2T(\frac{n}{2})+cn\\ &= 2(2T(\frac{n}{2^2})+c\frac{n}{2})+cn=2^2T(\frac{n}{2^2})+2cn \\ &= 2^2(2T(\frac{n}{2^3})+c\frac{n}{2^2})+2cn=2^3T(\frac{n}{2^3})+3cn \\ &= ... \\ &= 2^iT(\frac{n}{2^i})+icn \\ \end{aligned}$

at $i$-th level. since when $n=1$, we have $T(1)=c$, we can solve $1=\dfrac{n}{2^j}$ and get $j=\log n$, so

$T(n)=2^jT(1)+jcn=2^jc+jcn=cn+\log n\,cn\in\Theta(n\log n)$

solve with method 2

                   +----+cn +---+                 level 0: cn
                   v            v
         +------+cn/2         cn/2+-----+         level 1: 2*cn/2=cn
         |         +            +       |
         v         v            v       v
  +--+ cn/4      cn/4         cn/4     cn/4 +-+   level 2: 4*cn/4=cn
  |                                           |
.....           ......       ......         .....
  |                                           |       ...
  v                                           v
  c  c                .......              c   c  level logn: n*c=cn

first mergesort call have time cn (for merge), then it calls two mergesorts with size n/2, each of which has time cn/2, ...
all rows in fact sums to cn, there are logn+1 rows, so $T(n)=(\log n+1)cn$

useful formulas

some recurrence relations

useful sums

• arithmetic sequence

  $\sum_{i=0}^{n-1}(a+di)=na+\frac{dn(n-1)}{2}\in\Theta(n^2),d\neq 0$

• geometric sequence

  $\sum_{i=0}^{n-1}ar^n=\left\{\begin{matrix} a\dfrac{r^n-1}{r-1}&\in\Theta(r^n) & \text{ if } r>1\hphantom{--} \\ an\hphantom{--}&\in\Theta(n) & \text{ if } r= 1\hphantom{--}\\ a\dfrac{1-r^n}{1-r}&\in\Theta(1) & \text{ if } 0<r<1 \end{matrix}\right.$

• harmonic sequence

  $\sum_{i=1}^n\frac{1}{i}=\ln n+\gamma+o(1)\in\Theta(\log n)$

• few more

  $\sum_{i=1}^n\frac{1}{i^2}=\frac{\pi^2}{6}\in\Theta(1)$

  $\sum_{i=1}^ni^k\in\Theta(n^{k+1}),k\geq 0$

useful formulas

• $x-1<\lfloor x\rfloor\leq x$
• $x-1\leq\lceil x\rceil< x$

eg. $\log(n!)=\log n+\log(n-1)+...+\log 1\in\Theta(n\log n)$
proof.

• we have $f(n)=\log n+...+\log 1\leq \log n +...+\log n=n\log n\in\Theta(n\log n)$.
• if we choose $n\geq 4$, then $\log n\geq 2$ so $\log n-2\geq 0\Longrightarrow 2\log n-2\geq\log n\Longrightarrow \log n-1\geq\frac{1}{2}\log n\Longrightarrow \log n-\log 2\geq \frac{1}{2}\log n\Longrightarrow \log\frac{n}{2}\geq\frac{1}{2}\log n$ so $\frac{n}{2}\log\frac{n}{2}\geq\frac{1}{2}\frac{n}{2}\log n$.
  so $f(n)\geq \log n+...\log\frac{n}{2}\geq \log\frac{n}{2}+...+\log\frac{n}{2}=\frac{n}{2}\log\frac{n}{2}\geq \frac{1}{4}n\log n\in\Omega(n\log n)$. $\square$

eg. show $T(n)=2T(\frac{n}{2})+c$ reduces to $\Theta(n)$.
$T(n)=2^iT(\frac{n}{2^i})+(2^0+2^1+...+2^{i-1}),\,\forall i$. let $i=\log n$ we have $T(n)=nc+\sum_{k=0}^{\log n-1}2^k=nc+\frac{2^{\log n}-1}{2-1}=nc+(n-1)\in\Theta(n)$. $\square$

priority queues

review of ADTs

stack

• LIFO (last-in, first-out)
• push: insert element
• pop: remove element
• implementation: array

  +---+---+---+---+  push 3  +---+---+---+---+   pop    +---+---+---+---+
  | 1 | 8 |   |   |   +-->   | 1 | 8 | 3 |   |   +-->   | 1 | 8 |   |   |
  +---+---+---+---+          +---+---+---+---+          +---+---+---+---+
  top: 1                     top: 2                     top: 1
  

• implementation: linked list

  +---+  +---+  push 3  +---+  +---+  +---+    pop    +---+  +---+
  | 1 +->+ 8 |   +-->   | 3 +->+ 1 +->+ 8 |    +-->   | 1 +->+ 8 |
  +---+  +---+          +---+  +---+  +---+           +---+  +---+
    ^                     ^                             ^
  top                   top                           top
  

queue

• FIFO (first-in, first-out)
• enqueue: insert
• dequeue: remove the least recently iserted item
• implementation: (circular) array

  +---+---+---+---+ enqueue 3 +---+---+---+---+  dequeue +---+---+---+---+
  | 8 | 1 |   |   |    +-->   | 8 | 1 | 3 |   |   +-->   |   | 1 | 3 |   |
  +---+---+---+---+           +---+---+---+---+          +---+---+---+---+
  front: 0                    front: 0                   front: 1
  rear : 1                    rear : 2                   rear : 2
  

• implementation: linked list

  +---+  +---+ enqueue 3 +---+  +---+  +---+  dequeue  +---+  +---+
  | 8 +->+ 1 |    +-->   | 8 +->+ 1 +->+ 3 |    +-->   | 1 +->+ 3 |
  +---+  +---+           +---+  +---+  +---+           +-+-+  +---+
    ^      ^               ^             ^               ^      ^
  front  rear            front         rear            front  rear
  

binary tree

• a binary tree is either empty, or consists of a node and two binary trees left/right subtrees
• the height of a non-empty tree is the length of the longest path from root to node. the height of the empty tree is -1, the height of tree with one node is 0.
• a binary tree with n odes has height at least $\log(n+1)-1\in\Omega(\log n)$

pqueue

• insert: inserting an item tagged with a priority
• deleteMax: removing the item of highest priority
• priority is also called key
• application: 'todo' list, sorting

use pqueue to sort

PQsort(A[n]):
    auto PQ = new priority_queue
    for k = 0, n-1:
        PQ.insert(A[k], key=A[k])  // fill elements to pqueue
    for k = n-1, 0, -1:
        A[k] = PQ.deleteMax()

run-time: $O(\sum_{i=0}^n\texttt{insert}(i)+\sum_{i=0}^n\texttt{deleteMax}(i))$, depending on how we implement the pqueue

realizations of pqueues

realization 1: use unsorted array

• insert: O(1)
• deleteMax: O(n), because we search the array for one with max key
• PQsort with this realization yields selection sort, runtime is O(n^2)

realization 2: use sorted arrays

• insert: O(n), because we need to iterate elements to find where to put the new item, and probably shift existing items to give empty space
• deleteMax: O(1), simply remove the last entry
• PQsort with this realization yields insertion sort, runtime is O(n^2)

binary heap

• a certain type of binary tree with following properties
  • structural: all the levels of a heap are completely filled except (possibly) for the last level. the filled items in the last level are left-justified.
  • heap-order: for any node i, the key of the parent of i is larger than or equal to key of i.
• the max name is max-oriented binary heap

lemma. the height of a heap with $n$ nodes is $\Theta(\log n)$
proof. for a heap of height $h$, we have at least level 0(full) + level 1(full) + ... + level h-1(full) + level h(only 1) = $1+2+4+...+2^{h-1}+1=(2^h-1)+1=2^h$ nodes. and at most (all filled) = $1+2+4+...+h=2^{h+1}-1$ nodes.
hence we have $2^h\leq n\leq 2^{h+1}-1\leq 2^{h+1}$, which is $h\leq \log(n)\leq h+1$. rearrange we have $\log(n)-1\leq h\leq \log(n)$ so $h\in\Theta(\log n)$. $\square$

storing heaps in arrays

• let H be a heap of n items and let A be an array of size n. store root in A[0] and continue with elements level-by-level from top to bottom, in each level left-to-right
• the root node is at index $0$
• the left child of node i is node $2i+1$
• the right child of node i is node $2i+2$
• the parent of node i is node $\Bigl\lfloor\dfrac{i-1}{2}\Bigr\rfloor$
• the last node is $n-1$

Week 3. May 25

insert in heaps

• insert the node to the last position (n-1), it may break ordering. need to fix-up
• if it breaks ordering, swap with its parent, continue until it is less than parent
• the new item "bubbles up"

// k is an index corresponding to a node
fix_up(A[], k):
    while parent(k) exist and A[parent(k)] < A[k]: // worst: swap until it becomes root
        swap(A[k], A[parent(k)])
        k = parent(k)

insert(A[], n, item):
    increase size of A by 1
    auto l = last(n) // n-1
    A[l] = item
    fix_up(A, l)

worst time = O(height of heap) = (logn)

deleteMax in heaps

• the max item of a heap is the root node
• we replace root by the last leaf (n-1). breaks ordering. need to fix-down
• swap this new root with the larger of its children, continue until it is larger than children, or it becomes leaf

// k is an index corresponding to a node
fix_down(A[], n, k):
    while k is not leaf:
        // find child with larger key
        // there can't be case when left doesn't exist and right exist
        auto j = leftchild(k)
        if j != last(n) and A[j+1] > A[j]:
            j = j+1
        if A[k] >= A[j]: break
        swap(A[j], A[k])
        k = j

deleteMax(A[], n):
    auto res = A[root()]
    swap(A[root()], A[last(n)])
    decrease size by 1 // remove original root (now last)
    fix_down(A, n-1, root())
    return res

worst time = O(height of heap) = (logn)

pqsort

PQsortWithHeap(A[n]):
    auto hp = new heap
    for k = 0, n-1:
        hp.insert(key=A[k])  // just insert keys, no items
    for k = n-1, 0, -1:
        A[k] = hp.deleteMax()

• both insert and deleteMax is O(logn), so it takes O(nlogn) time. it takes O(n) extra space

heapsort

problem: given n items all at once, build a heap containing all of them

• naive: insert item one by one by calling fixup
• use fixdowns, start from second bottom

heapify(A[n] /* A is regular array */):
    for i = parent(last(n)), 0, -1:
        fix_down(A, i)
// worst time: O(n)

the running time of heapify $T(n)$ is $\Theta(n)$.
proof for $n=2^{h+1}-1$ (complete heap).

$\begin{aligned} T(n) &\in \Theta(\text{worst case number of swaps}) \\ &= \Theta(\text{level h, swap 0 times each + level h-1, 1 time each, + ... + level 0}) \\ &= \Theta(0\cdot 2^{h-0}+1\cdot2^{h-1}+2\cdot2^{h-2}+...+h\cdot2^{h-h}) \\ &= \Theta(2^h\sum_{i=0}^{h}\frac{i}{2^i}) \\ &= \Theta(2^h) = \Theta(n) \end{aligned}$

where each level $h-i$ has $2^{h-i}$ nodes. and $\sum_i\frac{i}{2^i}\leq 2$

we can use fix_ups, however, "The running time is at least nlogn. You can see this by noting there are n over two elements in the bottom layer, each of which are at a depth logn, which is the cost of a fixup operation."

heapsort(A[], n):
    heapify(A)                        // O(n)
    // repeatedly find max
    while n > 1:                      // O(nlongn)
        // delete max (put it to last, and fixdown skips it)
        swap(A[root()], A[last(n)])
        n--
        fix_down(A, n, root())

takes O(nlogn) time

find smallest item

problem: find the k-th smallest item in an array A of n distinct numbers

• sol1: make k passes through the array, deleting the minimum num each time
  • $\Theta(kn)$
• sol2: sort A, return A[n-k]
  • $\Theta(n\log n)$
• sol3: scan the array and maintain the k smallest numbers seen so far in a max-heap, finally take the root
  • $\Theta(n\log k)$
• sol4: create a min-heap with heapify(A). call deleteMin(A) k times
  • $\Theta(n+k\log n)$ best

sorting and randomized algorithms

selection problem: given an array A of n numbers, and $0\leq k<n$, find the element that would be at position k of the sorted array

• special case: median finding: $k=\left\lfloor\dfrac{n}{2}\right\rfloor$
• selection can be done with heaps with $\Theta(n+k\log n)$ (sol4)
• median-finding with this is $\Theta(n\log n)$ (same as sorting first)

quick-select

1. choose_pivot(A): return an index p in A. we use the pivot to rearrange the array

   // simplest
   choose_pivot(A[]) => A.size - 1
   

2. partition(a, p): rearrange A and return pivot index i so that
   • all items in A[0 : i-1] are less/eq than v
   • pivot value is in A[i]
   • all items in A[i+1 : n-1] are greater than v

easy partition: create smaller, equal, larger arrays separately, then concatenate them. O(n) time and space

efficient in-place partition

• keep swapping the outermost wrongly-positioned pairs

partition(A[n], p):
    swap(A[n-1], A[p])
    auto i = -1     // begin from left
    auto j = n-1    // begin from right
    auto v = A[n-1] // pivot index
    while true:
        // stop when A[i] is bigger than pivot
        do: i++ while i < n and A[i] < v
        // stop when A[j] is smaller than pivot
        do: j-- while j > 0 and A[j] > v
        // break if two pointers overlap, where two elems are in correct position
        if i >= j: break
        // swap wrongly positioned ones
        else: swap(A[i], A[j])
    swap(A[n-1], A[i])
    return i

takes $O(n)$.

quick-select 1

quick_select1(A[], k):
    // selects kth element as if A is sorted
    auto p = choose_pivot(A)
    auto i = partition(A, p)
    if i == k:
        return A[i]
    else if i > k:
        return quick_select1(A[:i-1], k)
    else:
        return quick_select1(A[i+1:], k-i-1) // note index relative to new subarray

running time analysis:

worst: list is sorted eg [1,2,3,4], and want to select 1st elem. choose pivot to be 4, then after partition the array is the same, qs recurses on [1,2,3], ... recursive call always have size n-1.

we have

$T(n)\begin{cases} T(n-1)+cn & \text{ , } x\geq 2 \\ c & \text{ , } x= 1 \end{cases} =cn+c(n-1)+c(n-2)+...+c\cdot 2+c\in\Theta(n^2)$

best: the chosen pivot is just the kth elem. no recursive call (just partition). $O(n)$.

average:

• simple assumption: all input numbers are distinct
• characterize input by sorting permutation: the permutation that would put the input in order
• assume all n! permutations are equally likely, then the average cost is (sum of costs of all perms) / n!

define $T(n,k)$ as average cost for selecting kth item from array of size n. then

• $T(1,k)=c$
  • size is 1
• $T(n,k)=cn+\frac{1}{n}\left( \sum_{i=0}^{k-1}T(n-i-1, k-i-1)+\sum_{i=k+1}^{n-1}T(i,k)\right)$
  • i is the choice of pivot (0, ..., n-1). there are n possibilities, so 1/n
  • if i < k, recurse on right subarray, cn+T(n-i-1,k-1-i)
  • if i = k, only partition, cn
  • if i > k, recurse on left subarray, cn+T(i,k)

theorem. $T(n,k)\leq 4cn$.
proof. use induction. base: if $n=1$, then $T(1,k)=c\leq 4c\cdot 1$.
inductive:

$\begin{aligned} T(n,k)&\leq cn+\frac{1}{n}\left(\sum_{i=0}^{k-1}4c(n-i-1)+\sum_{i=k+1}^{n-1}4ci\right)\\ &=cn+\frac{4c}{n}\left(\sum_{i=0}^{k-1}n-\sum_{i=0}^{k-1}(i+1)+\sum_{i=k+1}^{n-1}i\right)\\ &=cn+\frac{4c}{n}\left(nk-\frac{(1+k)k}{2}+\frac{(k+1+n-1)(n-1-k)}{2}\right)\\ &\leq cn+\frac{4c}{n}(nk-k^2+\frac{n^2}{2})\\ &=cn+\frac{4c}{n}\frac{n^2}{2}+\frac{4c}{n}(nk-k^2) \,\,(\text{maximized when }k=\frac{n}{2})\\ &\leq cn+2cn+\frac{4c}{n}(n\frac{n}{2}-\frac{n^2}{4})\\ &=cn+2cn+\frac{4c}{n}(\frac{n^2}{4})\\ &=4cn \end{aligned}$

$\square$

that is $T\in O(n)$.

Week 4. June 1

randomized algorithm

• once which relies on some random numbers in addition to the input
• the runtime depends on the input and the random number used
• goal: shift the dependency of runtime from what we can't control (input) to what we can control (random numbers)

defn. the expected running time is

$T^{\text{exp}}(I)=E[T(I,R)]=\sum_RT(I,R)\cdot Pr[R]$

where $T(I,R)$ is the running time of a randomized algorithm $A$ for an input instance $I$ and the sequence of random numbers $R$.

randomized quick-select

• goal: create a randomized version of quick_select for which all input has the same expected runtime

first idea: randomly shuffle the input

shuffle(A[]):
    for i = 0, n-2:
        swap(A[i], A[i+random(n-i)])

assuming the random(n) returns integers uniformly from 0, 1, ..., n-1.

• drawback: costly, tricky to analysis

second idea: random pivot by changing pivot selection

choose_pivot2(A[n]):
    return random(n)

quick_select2(A[], k):
    auto p = choose_pivot2(A)
    ...

the probability of choosing a pivot index i from 0 to n is $\frac{1}{n}$. so the analysis is the same as average case. expected runtime is $\Theta(n)$.

quick-sort

quick_sort1(A[n]):
    if n <= 1: return
    auto p = choose_pivot1(A) // last element
    auto i = partition(A, p)
    quick_sort1(A[:i-1])
    quick_sort(A[i+1:])

let $T(n)$ be the runtime for quick_sort1, then it depends on the pivot index i. we have

$T(n)=\Theta(n)+T(i)+T(n-i-1)$

worst-case: we always have i=0 or n-1

$T(n)\begin{cases} T(n-1)+cn & \text{ , } x\geq 2 \\ c & \text{ , } x= 1 \end{cases}$

similar to worst-case quick select $T(n)\in\Theta(n^2)$.

best-case: we always have i = $\lfloor\frac{n}{2}\rfloor$ or $\lceil\frac{n}{2}\rceil$

$T(n)=\begin{cases} T(\Bigl\lfloor\dfrac{n-1}{2}\Bigr\rfloor)+T(\Bigl\lceil\dfrac{n-1}{2}\Bigr\rceil)+cn &, n>1 \\ c &, n= 1 \end{cases}$

resolves to $\Theta(n\log n)$.

average-case: there are (n-1)! permutations have to pivot indices i

$\begin{aligned} T(n)&=\frac{1}{n!}\sum_{i=0}^{n-1}\sum_{\text{size of I is n, I has pivot i}}\text{running time for instance I} \\ &\leq\frac{1}{n!}\sum_{i=0}^{n-1}(n-1)!(cn+T(i)+T(n-i-1))\\ &=cn+\frac{1}{n}\sum_{i=0}^{n-1}(T(i)+T(n-i-1)) \end{aligned}$

theorem. $T(n)\in\Theta(n\log n)$.
proof. rewrite

$\begin{aligned} T(n)&=cn+\frac{2}{n}\sum_{i=0}^{n-1}T(i)\\ nT(n)&=cn^2+2\sum_{i=0}^{n-1}T(i)\\ (n-1)T(n-1)&=c(n-1)^2+2\sum_{i=0}^{n-2}T(i)\\ nT(n)-(n-1)T(n-1)&=c(2n-1)+2T(n-1)\\ nT(n)&=(n+1)T(n-1)+c(2n+1)\\ \frac{T(n)}{n+1}&=\frac{T(n-1)}{n}+\frac{c(2n-1)}{n(n+1)} \end{aligned}$

define $A(n)=\frac{T(n)}{n+1}$, we obtain

$\begin{aligned} A(n)&=A(n-1)+\frac{c(2n-1)}{n(n+1)}\\ &=A(n-2)+\frac{c(2(n-1)-1)}{(n-1)n}+\frac{c(2n-1)}{n(n+1)}\\ &...\\ &=c\sum_{i=1}^n\frac{2i-1}{i(i+1)}\\ &=2c\sum_{i=1}^n\frac{1}{i+1}-c\sum_{i=1}^n\frac{1}{i(i+1)}\\ &\rightarrow\Theta(\log n)+\Theta(1) \end{aligned}$

so $T(n)=(n+1)T(n)\in\Theta(n\log n)$. $\square$

optimizations:

• by using randomized choose_pivot2, the expected time for quicksort2 is O(nlogn).
• the auxiliary space is $\Omega$ (recursion depth)
  • this is $\Theta(n)$ in worst-case
  • it can be reduced to O(logn) worst-case by recurring in smaller sub-arrays first and replacing the other recursion by while loop
• once should stop recursing when $n\leq 10$. run insertion sort at then end then sorts everything in O(n) since all items are within 10 units of their required position
• arrays with many duplicates can be sorted faster by making partition to produce 3 subsets: <=v, ==v, >=v
• tricks that apply in many situations:
  • pass only range of indices instead of full array
  • avoid recursion altogether by keeping an explicit stack

quick_sort3(A[n]):
    auto S = new stack<pair<int, int>>
    S.push({0, n-1})
    while S is not empty:
        auto [l, r] = S.pop()
        while r-l+1 > 10:
            auto p = choose_pivot2(A, l, r)
            auto i = partition(A, l, r, p)
            if i-l > r-i:
                S.push({l, i-1})
                l = i+1
            else:
                S.push({i+1, r})
                r = i-1
    insertion_sort(A)

lower bounds for sorting

comparison-based sorting lower bound is O(nlogn)

• the comparison model data can only be assessed in two ways:
  • compare
  • swap/copy

theorem. any correct comparison-based sorting algorithm requires at least $\Omega(n\log n)$ comparison operations to sort $n$ distinct items.
proof. let $h$ be the max number of comparisons performed by the algorithm. in the decision tree, the number of leaves (permutations) $\geq n!$, and $\leq 2^h$. so $2^h\leq n!\Longrightarrow h\geq \log(n!)= \log n+\log(n-1)+...+\log(1)\geq\log n+\log(n-1)+...\log(\frac{n}{2}+1)\geq\frac{n}{2}\log(\frac{n}{2})=\frac{n}{2}\log n-\frac{n}{2}\in\Omega(n\log n)$. $\square$

non-comparison-based sorting can be O(n) under assumptions

• assume keys are numbers in base R (radix)
  • most common: 2, 10, 16, 128, 256
• assume all keys have the same number m of digits
  • eg: (R=4) [123, 230, 021, 320, 210, 232, 101]
• can sort base don individual digits

bucket sort (single digit)

• sorts numbers by a single digit
• create a "bucket" for each possible digit: array of linked lists, length R
• copy item with digit i into bucket B[i]
• at the end copy buckets in order into A

   A              B                              A
+-----+        +-----+                        +-----+
| 123 |        |B[0]  = 230 -> 320 -> 210     | 230 |
+-----+        +-----+                        +-----+
| 230 |        |B[1]  = 021 -> 101            | 320 |
+-----+        +-----+                        +-----+
| 021 |        |B[2]  = 232                   | 210 |
+-----+        +-----|                        +-----+
| 320 |  +-->  |B[3]  = 123           +-->    | 021 |
+-----+        +-----+                        +-----+
| 210 |                                       | 101 |
+-----+                                       +-----+
| 232 |                                       | 232 |
+-----+                                       +-----+
| 101 |                                       | 123 |
|-----|                                       +-----+
    ^
sort by this digit

// A: array of size n, contains numbers with digits in {0, ..., R-1}
// d: index of the digit by which we wish to sort
bucket_sort(A[n], d):
    auto B = new array<list<int>>(length=R) // space: R+n
    for i = 0, n-1:
        B[dth digit of A[i]].append(A[i])
    auto i = 0
    for j = 0, R-1:
        while B[j] is not empty:
            A[i++] = B[j].front
            B[j].front = B[j].next