Foundations of Algorithms Workshop 5 === ###### tags: `comp10002` `workshop` `c` --- - Algorithmic Complexity - Recurrence relations - Correctness of algorithms - Binary search - More arrays. --- ### Exercises - 1 & 4 in Lecture 5 - Chapter 7 Exercises (7.1-7.11) --- ### Algorithmic Complexity ```clike for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { printf("Bippity Boppity your CPU Cycles are my property\n") } } } ``` What is the complexity of this? --- ### Algorithmic Complexity $O(n^3)$ --- ### Algorithmic Complexity So usually we care about the rate of growth or more specifically the asymptotic time complexity of a function. $f(n) \in O(g(n))$ --- ### Big-O $f(n)$ **grows asymptotically no faster than** $g(n)$ if there exists two *positive constants* $c_1$ and $c_2$ such that: $f(n) \leq c_1 * g(n)$ holds for all $n \geq c_2$ --- ### Complexities of stuff - **Insertion Sort**: $O(n^2)$ - **Selection Sort**: $O(n^2)$ - **Quick Sort**: $O(n^2)$ ** - **Binary Search**: $O(logn)$ --- ### The other Big X's Big Omega $\Omega$ (no slower than) Big Theta $\Theta$ (both no faster and no slower than $f(n) \in \Theta \land f(n) \in \Omega$) Also ammortized, average cost etc. --- ### What is the complexity of the following in BIG O ```cpp int a = 0, b = 0; for (i = 0; i < N; i++) { a = a + rand(); } for (j = 0; j < M; j++) { b = b + rand(); } ``` --- ### What is the complexity of the following in BIG O ```cpp int fib(int n) { if (n < 1) return 0; if (n < 2) return 1; return fib(n-1) + fib(n-2); } ``` --- ### Complexity Classes $O(1)$ constant $O(log(n))$ logarithmic $O((log(n))c)$ polylogarithmic $O(n)$ linear $O(n^2)$ quadratic $O(n^c)$ polynomial $O(c^n)$ exponential --- ### What are the complexity classes of the following? 1. $\frac{n(n+1)}{2}$ 2. $n/2 + n/4 + n/8 + ...$ 3. $n^{0.5}$ 4. $T(n) = T(n/2) + 1$, $T(1) = 1$ --- ### Search We want to find the index of an element within a container, or if it doesn't exist. > What can we do here? --- ### Linear Search.. ```clike int key = (THING WE WANNA SEARCH FOR); for (int i=0;i<n;++i) if (vi[i] == key) return i; return -1; ``` --- ### We can do better > If the array is sorted then we can skip some stuff, e.g. for key = 19 left = 0, right = 8 [1,3,7,8,10,15,19,21] --- left = 0, right = 8, mid = 4 [1,3,7,8,{10},15,19,21] --- l = 5, r = 8, mid = 6 [1,3,7,8,10,15,{19},21] --- ### Binary Search ```clike while (l <= r) { mid = l + (r - l) / 2; if (v[i] == key) return i; if (v[i] > key) { r = mid - 1; } else { l = mid + 1; } } ``` --- ### B-Search Complexity We can work backwards, when we finish - we have a single element left (or none). At each stage we double the number of elements we consider. Hence $n^2$ in reverse so $log_2(n)$ in the normal direction. --- ### B-Search Recurrence Relation $T(n) =$ $1$ if $n < 1$ $1 + T(n/2)$ --- ### Quick Sort Basic idea: - Split your container into three segments, where $p$ is your partition. $>p$ $<p$ $=p$ - Appropriately rearrange elements such that for every element - the condition above holds. --- ### Quick Sort Algo let $p$ = $A[n-1]$ (last element) ```python def q_sort(vi[], l, r): if (l < r): p = partition(vi, l, r) q_sort(vi, l, p-1) q_sort(vi, p+1, r) ``` --- ### Quick Sort Algo ```python def partition(vi[], l, r): p = vi[r] i = l-1 for j in range(l,r-1): if vi[j] < p: ++i swap(vi[i], vi[j]) swap(vi[i+1], vi[r]) return i+1 ``` --- ### Example ``` [10,80,30,90,40,50,70] ``` --- ### Lecture 5 Ex. 1 > Suppose that the sorted array may contain duplicate items. Linear search will find the first match.Modify the binary search algorithm so that it also identifiesthe first match if there are duplicates. Modify the demonstration of correctness so that it matches your altered algorithm. --- ### Lecture 5 Ex. 4 > Suppose that the kth smallest item is to be identified in an unsorted array A [0...n−1]. > Design and analyze an algorithm for this problem that requires O(nk) time in the worst case. > Design and analyze an algorithm for this problem that requires O(n) time in the average case --- ### Exercises in Chapter 7 7.9 Ascending Runs 7.10 Number of Inversions 7.5 Student Numbers