# Design and Analysis of Algorithms

## Lecture 0 <2019-08-26 Mon>

• Syllabus review
• Course Webpage
• Proof-heavy course
• Design – methods used to create new algorithms
• Analysis – Mathematical assessment of an algorithm’s correctness and efficiency
• Correctness – Does it do what it’s supposed to do on all possible inputs?
• Efficiency – Measure the algorithm’s running time, counting the number of basic operations

## Lecture 1 <2019-08-26 Mon>

### Asymptotic Notation – Starts on Slide 3

• Big-$$O$$
• Big-$$\Omega$$
• Big-$$\Theta$$
• Little-$$o$$
• Little-$$\omega$$
• Not Interchangeable
• Asymptotic Upper Bound – Big-$$O$$, $$O(g(n)) = \{f(n) : \exists c, n_0 > 0 \mid \forall n \geq n_0, 0 \leq f(n) \leq cg(n) \}$$
• Asymptotic Lower Bound, Big-$$\Omega$$, $$\Omega(g(n)) = \{f(n) : \exists c, n_0 \mid \forall n \ge n_0, 0 \leq cg(n) \leq f(n) \}$$
• Asymptotic Tight Bound, Big-$$\Theta$$, $$\Theta(g(n)) = \{f(n) : \exists c_1, c_2, n_0 > 0 \mid \forall n \geq n_0, 0 \leq c_1 g(n) \leq f(n) \leq c_2 g(n) \}$$
• Upper Bound, not tight, little-$$o$$
• Lower bound, not tight, little-$$\omega$$

## Lecture 1, Cont. <2019-08-28 Wed>

### Upper And Lower Bounds

• 01.9
• Analyze algorithms and problems in terms of time complexity (count of operations)
• Sometimes in space complexity (memory usage)
• upper and lower bounds are used
• applies to general problems
• 01.10 – upper is most common form
• Algorithm $$A$$ has an upper bound of $$f(n)$$ for input of size $$n$$ if there exists no input of size $$n$$ such that $$A$$ requires more than $$f(n)$$ time
• Consider sort, Quicksort and Bubblesort are $$\mathcal{O}(n^2)$$, and Mergesort is $$\mathcal{O}(n \log{n})$$
• Quicksort is used more often in practice, when randomized tends to be closer to $$n \log{n}$$ time
• Lower Bounds are like best-case results, typically not as interesting
• 01.11 – Uppper bound of a problem
• A problem has an upper bound of $$f(n)$$ if there exists at least one algorithm that has an uppperbound $$f(n)$$
• there exists an algorithm with time/space complexity of at most $$f(n)$$ on all inputs of size $$n$$
• Mergesort has worst-case $$\mathcal{O}(n \log{n})$$, sorting has an upper bound of $$\mathcal{O}(n \log{n})$$
• 01.12 – Lower bounds of a problem
• A problem has a lower bound of $$f(n)$$ if, for any algorithm $$A$$, to solve it, there exists at least one input of size $$n$$ that forces $$A$$ to take at least $$f(n)$$ time/space.
• Called the pathological input, depends on $$A$$ itself.
• input of size $$n$$ (reverse) that forces Bubblesort to take $$\Omega(n^2)$$
• Since every sorting algorithm has an input of size $$n$$ forcing $$\Omega(n \log{n})$$ steps, the sorting problem has a time comlpexity lower bound of $$\Omega(n \log{n})$$. Therefore, Mergesort is asymptotically optimal.
• 01.13 Lower Bounds, 2
• To argue a lower bound, use adversarial argument: algorithm simulates an arbitrary algorithm $$A$$ to build pathological input
• Needs to be a general form, pathological input depends on specific algorithm $$A$$
• Can reduce one problem to another to establish lower bounds
• Show that if we can compute convex hull in $$o(n \log{n})$$ time, then we can sort in time $$o(n \log{n})$$; cannot be true, so convex hull takes $$\Omega(n \log{n})$$

### Efficiency

• 01.14 – Efficiency
• An algorithm is time- or space- efficient if worst case time/space complexity is $$\mathcal{O}(n^c)$$ for constant $$c$$ and input size $$n$$, polynomial in the input size
• Input size on in number of bits needed
• graph of $$n$$ nodes takes $$\mathcal{O}(n \log{n})$$ bits to represent nodes, $$\mathcal{O}(n^2 \log{n})$$ to represent edges., algorithm in $$\mathcal{O}(n^c)$$ is efficient
• Problem that includes as an input a number, $$k$$ (e.g., threshold) onnly needs $$\mathcal{O}(\log{k})$$ bits to represent, efficient must run in $$\mathcal{O}(\log^c{k})$$
• If polynomial in $$k$$, called pseudopolynomial

### Recurrence Relations

• 01.15 – Recurrence Relations
• Non-recursive relations are relatively easy to analyse.
• Recurrence relations are used for time complexity of recursive algorithms, bound relation asymptotically
• For example, Mergesort
• $$T(n) = 2 T(n/2) + \mathcal{O}(n)$$
• Bound on $$T(n)$$ needed
• Use the Master theorem (See 235/156 notes)
• Other approaches include 01.17–18

### Graphs

• 01.19–24 – Graphs
• Set of vertices $$V$$, set of unordered pairs between vertices $$E$$ (edges)
• Directed graph has ordered pairs
• Weighted is directed augmented with weights for edges
• Adjacency list, each vertex has linked list listing edges, $$\mathcal{O}(n + m)$$
• Adjacency matrix, $$n \times n$$ – $$\mathcal{O}(n^2)$$

## Lecture 1, Cont. <2019-08-30 Fri>

### Graphs

• $$n \times n$$ matrix $$M$$, $$M(i,j) = w$$ for weight, $$\infty$$ for non-edges, takes $$\Theta(n^2)$$ space

### Algorithmic Techniques, Dynamic Programming

• 01.25
• Technique for solving optimization problems, where a best solution is needed, evaluated by an objective function
• Decomposes a problem into subproblems, optimally solves recursively, combines into final/optimal solution
• Exponential number of subproblems, many overlap, re-use solutions
• Number of distinct subproblems is polynomial
• Works if they have optimal substructure property – optimal solution is made up of optimal solutions to subproblems
• All-pairs shortest paths, knapsack
• Can prove correctness if optimal substructure property exists
• Must be careful, very carefully proven

### Algorithmic Techniques, Greedy Algorithms

• 01.26
• Must consider optimal substructure property
• Each step, commits to locally optimal
• Tend to be very quick, does not use all possible subproblems
• MST, Dijkstra’s

### Divide And Conquer

• 01.27
• Not limited to optimization, solve each sub-problem recursively, then combine
• Think Mergesort

• 01.28
• Assume opposite of premise to be proved, arrive at a contradiction of some other assumption
• To prove there is no greatest even integer:
• Assume for a reductio that there exists a greatest even integer $$N$$, for all even integers, $$n$$, we have $$N \geq n$$. (1)
• But $$M = N + 2$$ is an even integer, since it’s the sum of two even integers, and $$M > N$$.
• Therefore, (1) is false, so there is no greatest even integer. $$\box$$

### Proof by Induction

• 01.29
• Base case, and inductive step, involves non-negative integers
• Useful for proving invariants in algorithms, properties that always hold at every step (especially at the final step)
• See PHIL 411 notes

### Proof by Construction

• 01.30
• Proof of existence by directly constructing it.
• Will be used extensively for NP-completeness

### Proof by Contraposition

• 01.31
• $$P \to Q \equiv \lnot Q \to \not P$$
• Proof that if $$x^2$$ is even, then $$x$$ is even. Contraposition is the simplest
• Useful for proving biconditionals as well
• Useful for NP-completeness

## Lecture 2: Medians and Order Statistics <2019-08-30 Fri>

• Given an array $$A$$ of $$n$$ distinct numbers, $i$th order statistic of $$A$$ is its $i$th smallest element
• $$i = 1$$ – minimum
• $$i = n$$ – max
• $$i = \lfloor (n+1)/2 \rfloor$$ – (lower) median
• Given array $$A$$ of $$n$$ elements and a number $$i \in \{1, \dots, n\}$$ find the $i$th order statistic of $$A$$
• Can we do better?
• Minimum, linear, normal just scan through the array, keeping track of the smallest so far
• small is smallest from $$A_1$$ to $$A_i$$ – the loop invariant
• Loop invariant can be shown easily via induction
• Correctness by observing $$i = n$$ at the end, but before return
• $$\Theta(n)$$ – Cannot do better
• Must find a lower bound
• Must make at least $$n - 1$$ comparisons
• no element can be eliminated until shown it’s greater than at least one other element
• All still eligible to be smallest are in a bucket, removed after shown to be $$>$$ another.
• Each comparison removes at most one element, from the bucket, therefore at least $$n - 1$$ comparisons are needed to remove all but one from the bucket
• Follows by pigeonhole principle
• Minimum and Maximum (02.06)
• Given $$A$$ with $$n$$ elementts, find both min and max
• Obvious algorithm, non asymptotic time complexity
• Do better by checking for both
• Look at 02.07

## Lecture 2: Medians and Order Statistics, Continued <2019-09-04 Wed>

### The simultaneous Minimum and Maximum (starts 02.06)

• find-min and find-max are optimal, as they are at $$n - 1$$ comparisons for $$n$$ elements.
• Algorithm presented on 02.07 – be familiar with the algorithm (retype later)

(defun min-and-max (list-of-nums)
  (let ((len (length list-of-nums))
        (max (max (first list-of-nums)
                  (second list-of-nums)))
        (min (min (first list-of-nums)
                  (second list-of-nums))))
    (do ((i 1 (1+ i)))
        ((= i (1- (floor len 2))))
      (setq max (max max
                     (nth list-of-nums (* 2 i))
                     (nth list-of-nums (- (* 2 i) 1)))
            min (min min
                     (nth list-of-nums (* 2 i))
                     (nth list-of-nums (- (* 2 i) 1)))))
    (when (oddp len)
      (setq max (max max (nth list-of-nums (1- len)))
            min (min min (nth list-of-nums (1- len)))))
    (values max min)))

• For this algorithm, in $$\mathcal{O}(\frac{3}{2}n)$$

### Selection of $i$th smallest value (02.10)

• Select $i$th smallest value. Obvious solution (sort, return $i$th element), complexity is $$\Theta(n \log n)$$
• Can do better, running in linear time
• Uses divide-and-conquer, similar to binary search
• Definition on 02.12
• Uses partition like in quicksort (deterministic)
• $$q$$ from algorithm is in its final sorted position
• Select calls partition, choses pivot element $$q$$, reorders $$A$$ such that all elements $$< A_q$$ to the left of $$A_q$$ and all elements $$> A_q$$ to the right
• If $$A_q$$ is the element, return, if it’s greater learch left, less, search right.
• Partition chooses a pivot element $$A_x$$, exchange $$A_x$$ and $$A_r$$, then begin to loop to exchange appropriately

## Lecture 2: Medians and Order Statistics, Continued <2019-09-06 Fri>

### Selection, Continued

• Recall algorithm, from 02.12
• Requires partition, defined later on
• Partition chooses the pivot element
• Partition helps to preserve the invariant
• Choce of pivot element is crucial

### Choosing a Pivot element

• choise is critical to low time-complexit
• best choice of pivot element to partition
• Use the median – circular to do this
• Median of Medians
• $$A$$ of $$n$$ elements, partition $$A$$ into $$m = \lfloor n/3 \rfloor$$ groups of 5 elements, atnd at most one othe group of $$n \mod 3$$ elements
• $$A^{\prime} = [ x_1, x_2, \ldots, x_{\lceil n / 5 \rceil}]$$, where $$x_i$$ is median of group $$i$$ from sorting $$i$$
• $$y = \mathrm{Select}(A^{\prime}, 1, \lceil n/5 \rceil, \lfloor(\lceil n/5 \rceil + 1)/2 \rfloor)$$ is the pivot element, scan $$A[p \cdots r]$$ and return $$y$$ in as $$i$$ – this is choose pivot element
• As a team, do 02.19

### Time Complexity

• See 02.20
• Recurrence form (02.22):
• $$T(n)$$ total time for size $$n$$
• Pivot selection takes $$\mathcal{O}(n)$$ to split and $$T(n/5)$$ for finding median of medians, partitioning $$n$$ elements takes $$\mathcal{O}(n)$$ time
• Recursive select takes $$T(3n/4)$$ (in choose pivot element)
• ∴, $$T(n) \leq T(n/5) + T(3n/4) + \mathcal{O}(n)$$
• Or, rewritten as $$T(\alpha n) + T(\beta n) + O(n)$$ where $$\alpha = 1/5$$ and $$\beta = 3/4$$
• By theorem from Lecture 1, when $$\alpha + \beta < 1$$, $$T(n) \in \mathcal{O}(n)$$
• And thus, Select has complexity $$\mathcal{O}(n)$$
• Proof shown on 02.23
• How can we lower-bound to 1/4 of the elements – see 02.21

## Lecture 2: Medians and Order Statistics, Continued <2019-09-09 Mon>

### Practice, Median of Medians, 02.19

• $$A = [4, 9, 12, 17, 6, 5, 21, 14, 8, 11, 13, 29, 3]$$
• select(A, 1, 13, 4)
• Partition(A, 1, 13)
• ChoosePivotElement(A, 1, 13)
• $$[4, 9, 12, 17, 6], [5, 21, 14, 8, 11], [13, 29, 3]$$
• $$[9, 11, 13]$$
• $$11$$ is median, $$x = 10$$
• Proceed to swap
• $$A = [4, 9, 6, 3, 8, 11, 12, 17, 21, 14, 13, 29]$$, $$p = 6$$, $$k = 5$$
• Make sure to use lower median!

## Lecture 3: Dynamic Programming <2019-09-09 Mon>

• solving optimization problems
• Decompose problem into subproblems, solving them recursively and combine the solutions into a final, optimal solution
• exponential number of subproblems to solve, but with overlap, means solutions can be resued
• Number of distinct subproblems is polynomial

### The Rod cutting problem

• Rod of length $$n$$, cut into integer length smaller rods to maximize profit.
• Rod of length $$i$$ has price $$p_i$$
• Cuts are free, profit base solely on prices charged for rods
• Cuts only occur at integral boundaries, so there are $$n - 1$$ positions to cut, total number of possible solutions is $$2^{n - 1}$$
• Cuts $$i_1, \ldots, i_k$$, ($$i_1 + \cdots i_k = n$$), and revenue $$r_n = p_{i_1} + \cdots p_{i_k}$$ is maximized
• Optimal substructure problem

## Lecture 3: Dynamic Programming, Continued <2019-09-11 Wed>

### Rod cutting, an implementation

• Recall the optimal substructure property, an optimal solution is made up of optimal solutions to subproblems
• Easy to prove via contradiction
• $$r_n = \mathrm{max}(p_n, r_1 + r_{n - 1}, \ldots, r_{n - 1} + r_1)$$
• Helpful to simply store previously calculated values

## Lecture 3: Dynamic Programming, Continued <2019-09-13 Fri>

### Rod Cutting, continued

• Requires considering all possibilities (with one initial cut) for a given $$r_n$$, which gives two subproblems.
• Proof of correctness/proof of optimal substructure property by contradiction
• Assume for a reductio that the solution is not optimal for the subproblem…
• Some dynamic programming problems can be consider slightly differently.
• $$r_n = \max_{1 \leq i \leq n} (p_i + r_{n-i})$$ is an alternative form (03.05)
• Rod cutting proof available in book, §15.1 (p. 362)
• Cut-rod on (03.06)
• Missing memoization

### Time Complexity

• $$T(0) = 1$$, See 03.07
• Non-memoized complexity is huge
• Top-down with memoization
• Bottom-up, fill in table
• Have the same running time
• Memoized (recursive) implementation at 03.10
• Bottom up at 03.11 – easier to analyse

### Reconstructing a solution

• add a second array $$s$$ to keep track of the optimal size of the first piece cut in each subproblem
• Printing from this table is reasonably simple

## Lecture 3: Dynamic Programming, Continued <2019-09-16 Mon>

### Matrix Chain Multiplication

• long chain of $$n$$ matrices we want to multiply
• $$p \times q$$ by $$q \times r$$ requires $$pqr$$ steps
• Brute force solution is $$\Omega(4^n / n^{3/2})$$
• Steps:
1. Characterize structure of an optimal solution
2. Recursively define the value of an optimal solution
3. Compute the value of an optimal solution
4. Construct an optimal solution from computed information (03.18)
• Step 1
• $$A_{i \dots j}$$ is the matrix from $$A_i A_{i + 1} \cdots A_j$$
• Must split product and compute i to k and k+1 to j, then multiply the two together
• $$k$$ is the optimal parenthesization
• Assume cost is not optimal, then there exists some other solution from $$i$$ to $$k$$ such that $$cost(s^{\prime}) < cost(s)$$
• Then replace $$s$$ with $$s^{\prime}$$
• Step 2:
• $$m[i, j]$$ is min number of mults for Ai to Aj
• $$m[i, j]$$
1. $$i = j$$ = 0
2. $$i < j$$, split at $$k$$, $$m[i, j] = m[i, k] + m[k + 1, j] + p_{i - 1}p_{k}p_j$$
3. $$k$$ must be tried for all possible values, store in $$s[i, j]$$ to find $$k$$ for a given $$i, j$$ pair. (03.20)
• Step 3:
• Is $$\Theta(n^2)$$
• Bottom-up is on chain length
• Linear to solve each problem, a quadratic number of subproblems, ∴, $$\Theta(n^3)$$
• Implementation on 03.22