# Design and Analysis of Algorithms

## Table of Contents

- Lecture 0
- Lecture 1
- Lecture 1, Cont.
- Lecture 1, Cont.
- Lecture 2: Medians and Order Statistics
- Lecture 2: Medians and Order Statistics, Continued
- Lecture 2: Medians and Order Statistics, Continued
- Lecture 2: Medians and Order Statistics, Continued
- Lecture 3: Dynamic Programming
- Lecture 3: Dynamic Programming, Continued
- Lecture 3: Dynamic Programming, Continued
- Lecture 3: Dynamic Programming, Continued

## Lecture 0

- 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

### 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.

### 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\)

- there exists an algorithm with time/space complexity of at most \(f(n)\) on
- 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})\)

- To argue a lower bound, use adversarial argument: algorithm simulates an

### 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.

### Graphs

- 01.24 – Adjacency matrices
- \(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

### Proof By Contradiction

- 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\)

- Assume for a

### 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

- 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

### 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

### 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

### 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\)

- ChoosePivotElement(A, 1, 13)

- Partition(A, 1, 13)
- Make sure to use lower median!

## Lecture 3: Dynamic Programming

- 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

### 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

### 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…

- Assume for a
- 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

### 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:
- Characterize structure of an optimal solution
- Recursively define the value of an optimal solution
- Compute the value of an optimal solution
- 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 A
_{i}to A_{j} - \(m[i, j]\)
- \(i = j\) = 0
- \(i < j\), split at \(k\), \(m[i, j] = m[i, k] + m[k + 1, j] + p_{i - 1}p_{k}p_j\)
- \(k\) must be tried for all possible values, store in \(s[i, j]\) to find \(k\) for a given \(i, j\) pair. (03.20)

- \(m[i, j]\) is min number of mults for A
- 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