**Problem**: binary relationship from inputs to outputs**Algorithm**: procedure mapping each input to a single output- An algorithm
**solves**a problem if it returns a correct output for each and every problem input

- An algorithm
**Correctness**:- For small inputs: can use case analysis
- For arbitrarily large inputs: algorithm either is recursive or loop in some way. Use
**induction**.

**Efficiency**: how fast does an algorithm produce a correct output?- Count the number of fixed time operations algorithm takes to return
**Asymptotic Notation**: ignore constant factors and low order terms

input constant logarithmic linear log-linear quadratic polynomial exponential $n$ $\Theta (1)$ $\Theta (logn)$ $\Theta (n)$ $\Theta (nlogn)$ $\Theta ({n}^{2})$ $\Theta ({n}^{c})$ ${2}^{\Theta}({n}^{c})$ $1000$ $1$ $\approx 10$ $1000$ $\approx 10,000$ $1,000,000$ ${1000}^{c}$ ${2}^{1}000\approx {10}^{3}01$ Time $1ns$ $10ns$ $1\mu s$ $10\mu s$ $1ms$ ${10}^{(}3c-9)s$ ${10}^{2}81millenia$ **Model of Computation**: what operations on the machine can be performed in time.$O(1)$ Machine word: block of w bits (w is word size of a w-bit Word-RAM)

Memory: Addressable sequence of machine words

Processor supports many constant time operations on a

number of words (integers):$O(1)$ - integer arithmetic: (+, -, *, //, %)
- logical operators: (&&, ||, !, ==, <, >, <=, =>)
- bitwise arithmetic: (&, |, <<, >>, ...)
- Given word a, can read word at address a, write word to address a

**Data Structure**: a way to store non-constant data, that supports a set of operationsA collection of operations is called an

**interface**Example:

**Sequence**: Extrinsic order to items (first, last, nth)**Set**: Intrinsic order to items (queries based on item keys)

Data structures may implement the same interface with different performance

Example: Static Array - fixed width slots, fixed length, static sequence interface

`StaticArray(n)`

: allocate static array of size n initialized to 0 in time$\Theta (n)$ `StaticArray.get_at(i)`

: return word stored at array index i in time$\Theta (1)$ `StaticArray.set_at(i, x)`

: write word x to array index i in time$\Theta (1)$

: Notation$O$ - Non-negative function
is in$g(n)$ if and only if there exists a positive real number$O(f(n))$ and positive integer$c$ such that${n}_{0}$ for all$g(n)\le c\xb7f(n)$ .$n\ge {n}_{0}$

- Non-negative function
: Notation$\Omega $ - Non-negative function
is in$g(n)$ if and only if there exists a positive real number c and positive integer$\Omega (f(n))$ such that${n}_{0}$ for all$c\xb7f(n)\le g(n)$ .$n\ge {n}_{0}$

- Non-negative function
:$\Theta Notation$ - Non-negative
is in$g(n)$ if and only if$\Theta (f(n))$ $g(n)\in O(f(n))\cap \Omega (f(n))$

- Non-negative

- A
**data structure**is a way to store data, with algorithms that support**operations**on the data - Collection of supported operations is called an
**interface**(also**API**or**ADT**) - Interface is a
**specification**: what operations are supported (the problem!) - Data structure is a
**representation**: how operations are supported (the solution!)

- Maintain a sequence of items (order is
**extrinsic**) - Ex: (
,${x}_{0}$ ,${x}_{1}$ , . . . ,${x}_{2}$ ) (zero indexing)${x}_{n-1}$ - (use n to denote the number of items stored in the data structure)
- Supports sequence operations:

Type | Interface | Specification |
---|---|---|

Container | `build(X)` | given an iterable X, build sequence from items in X |

`len()` | return the number of stored items | |

Static | `iter_seq()` | return the stored items one-by-one in sequence order |

`get_at(i)` | return the | |

`set_at(i, x)` | replace the | |

Dynamic | `insert_at(i, x)` | add |

`delete_at(i, x)` | remove and return the | |

`insert_fist(x)` | add | |

`delete_first(x)` | remove and return the first item | |

`insert_last(x)` | add | |

`delete_last(x)` | remove and return the last item |

Special case interfaces:

**stack**:`insert_last(x)`

and`delete_last()`

**queue**:`insert_last(x)`

and`delete_first()`

Sequence about

**extrinsic**order, set is about**intrinsic**orderMaintain a set of items having

**unique keys**(e.g., item x has key x.key)(Set or multi-set? We restrict to unique keys for now.)

Often we let key of an item be the item itself, but may want to store more info than just key

Supports set operations:

Type Interface Specification Container `build(X)`

given an iterable X, build sequence from items in X `len()`

return the number of stored items Static `find(k)`

return the stored item with key k Dynamic `insert(x)`

add x to set (replace item with key x.key if one already exist) `delete(x)`

remove and return the stored item with key k Order `iter_ord()`

return the stored items one-by-one in key order `find_min()`

return the stored item with smallest key `find_max()`

return the stored item with largest key `find_next(k)`

return the stored item with smallest key larger than k `find_prev(k)`

return the stored item with largest key smaller than k Special case interfaces:

**dictionary**: set without the Order operations

Array is great for static operations!

`get at(i)`

and`set at(i, x)`

in`Θ(1)`

time!But not so great at dynamic operations...

(For consistency, we maintain the invariant that array is full)

Then inserting and removing items requires:

- reallocating the array
- shifting all items after the modified item

Sequence Data Structure | API Type | Worst Case | |||
---|---|---|---|---|---|

Array | Container | Static | Dynamic | ||

API | `build(x)` | `get_at(i)` `set_at(i)` | `insert_first(x)` `delete_first()` | `insert_last(x)` `delete_last()` | `insert_at(i, x)` `delete_at(i)` |

Array |

- Pointer data structure (this is
**not**related to a Python “list”) - Each item stored in a
**node**which contains a pointer to the next node in sequence - Each
`node`

has two fields:`node.item`

and`node.next`

- Can manipulate nodes simply by relinking pointers!
- Maintain pointers to the first node in sequence (called the head)
- Can now insert and delete from the front in
time! Yay!$\Theta (1)$ - (Inserting/deleting efficiently from back is also possible; you will do this in PS1)
- But now
`get_at(i)`

and`set_at(i, x)`

each take time... :($O(n)$ - Can we get the best of both worlds? Yes! (Kind of...)

Sequence Data Structure | API Type | Worst Case | |||
---|---|---|---|---|---|

Array | Container | Static | Dynamic | ||

API | `build(x)` | `get_at(i)` `set_at(i)` | `insert_first(x)` `delete_first()` | `insert_last(x)` `delete_last()` | `insert_at(i, x)` `delete_at(i)` |

Linked List |

- Make an array efficient for
**last**dynamic operations - Python “list” is a dynamic array
**Idea!**Allocate extra space so reallocation does not occur with every dynamic operation**Fill ratio**: the ratio of items to space$0\le r\le 1$ - Whenever array is full (
), allocate$r=1$ extra space at end to fill ratio$\Theta (n)$ (e.g., 1/2)${r}_{i}$ - Will have to insert
items before the next reallocation$\Theta (n)$ - A single operation can take
time for reallocation$\Theta (n)$ - However, any sequence of
operations takes$\Theta (n)$ time$\Theta (n)$ - So each operation takes
time “on average”$\Theta (1)$

Sequence Data Structure | API Type | Worst Case | |||
---|---|---|---|---|---|

Array | Container | Static | Dynamic | ||

API | `build(x)` | `get_at(i)` `set_at(i)` | `insert_first(x)` `delete_first()` | `insert_last(x)` `delete_last()` | `insert_at(i, x)` `delete_at(i)` |

Dynamic Array |

- Data structure analysis technique to distribute cost over many operations
- Operation has
**amortized cost** if k operations cost at most$T(n)$ $\le kT(n)$ - “
amortized” roughly means$T(n)$ “on average” over many operations$T(n)$ - Inserting into a dynamic array takes
amortized time$\Theta (1)$

- Delete from back?
time without effort, yay!$\Theta (1)$ - However, can be very wasteful in space. Want size of data structure to stay
$\Theta (n)$ **Attempt**: if very empty, resize to r = 1. Alternating insertion and deletion could be bad...**Idea!**When , resize array to ratio$r<{r}_{d}$ where${r}_{i}$ (e.g.,${r}_{d}<{r}_{i}$ )${r}_{d}=1/4,{r}_{i}=1/2$ - Then
cheap operations must be made before next expensive resize$\Theta (n)$ - Can limit extra space usage to
for any$(1+\epsilon )n$ (set$\epsilon >0$ )${r}_{d}=\frac{1}{1+\u03f5},{r}_{i}=\frac{{r}_{d}+1}{2}$ - Dynamic arrays only support dynamic last operations in
time$\Theta (1)$ - Python List append and pop are amortized
time, other operations can be$O(1)$ !$O(n)$ - (Inserting/deleting efficiently from front is also possible; you will do this in PS1)

Sequence Data Structure | API Type | Worst Case | |||
---|---|---|---|---|---|

Array | Container | Static | Dynamic | ||

API | `build(x)` | `get_at(i)` `set_at(i)` | `insert_first(x)` `delete_first()` | `insert_last(x)` `delete_last()` | `insert_at(i, x)` `delete_at(i)` |

Static Array | |||||

Linked List | |||||

Dynamic Array |

Storing items in an array in arbitrary order can implement a (not so efficient) set

Stored items sorted increasing by key allows:

- faster find min/max (at first and last index of array)
- faster finds via binary search:
$O(logn)$

Set Data Structure | API Type | Worst Case | |||
---|---|---|---|---|---|

Set | Container | Static | Dynamic | ||

API | `build(x)` | `find(k)` | `insert(k)` `delete(k)` | `find_min()` `find_max()` | `find_prev(k)` `find_next(k)` |

Array | |||||

Sorted Array |

- But how to construct a sorted array efficiently?

Given a sorted array, we can leverage binary search to make an efficient set data structure.

**Input**: (static) array A of n numbers**Output**: (static) array B which is a sorted permutation of A**Permutation**: array with same elements in a different order**Sorted**:`B[i - 1]`

≤`B[i]`

for all$i\in 1,...,n$

Example:

$[8,2,4,9,3]\to [2,3,4,8,9]$ A sort is

**destructive**if it overwrites (instead of making a new array$A$ that is a sorted version of$B$ )$A$ A sort is

**in place**if it uses extra space (implies destructive: in place ⊆ destructive)$O(1)$

- There are
permutations of A, at least one of which is sorted. (Due to duplications)$n!$ - For each permutation, check whether sorted in
$\Theta (n)$ - Example:
$[2,3,1]\to [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$

`def permutation_sort(A):`

` """Sort A"""`

` for B in permutations(A): # O(n!)`

` if is_sorted(B): # O(n)`

` return B`

permutation sort analysis:

- Correct by case analysis: try all possibilities (Brute Force)
- Running time:
which is exponential :($\Omega (n!\xb7n)$

**Substitution**: Guess a solution, replace with representative function, recurrence holds true**Recurrence Tree**: Draw a tree representing the recursive calls and sum computation at nodes**Master Theorem**: A formula to solve many recurrences (R03)

- Find a largest number in prefix
`A[:i + 1]`

and swap it to`A[i]`

- Recursively sort prefix
`A[:i]`

- Example:
$[8,2,4,9,3],[8,2,4,3,9],[3,2,4,8,9],[3,2,4,8,9],[2,3,4,8,9]$

`xxxxxxxxxx`

`def selection_sort(A, i=None):`

` """Sort A[:i+1]"""`

` if i is None: i = len(A) - 1`

` if i > 0:`

` j = prefix_max(A, i)`

` A[i], A[j] = A[j], A[i]`

` selection_sort(A, i - 1)`

` `

`def prefix_max(A, i):`

` """Return index of maximum in A[:i+1]"""`

` if i > 0:`

` j = prefix_max(A, i - 1)`

` if A[i] < A[j]:`

` return j`

` return i`

`prefix_max`

analysis:Base case: for

`i = 0`

, array has one element, so index of max is$i$ Induction: assume correct for

, maximum is either the maximum of$i$ `A[:i]`

or`A[i]`

, returns correct index in either case.**□**$S(1)=\Theta (1);S(n)=S(n-1)+\Theta (1)$ - Substitution:
,$S(n)=\Theta (n)$ $cn=\Theta (1)+c(n-1)=\Rightarrow 1=\Theta (1)$ - Recurrence tree: chain of
nodes with$n$ work per node,$\Theta (1)$ ${\mathrm{\Sigma}}_{i=0}^{n-1}1=\Theta (n)$

- Substitution:

- Recursively sort prefix
`A[:i]`

- Sort prefix
`A[:i + 1]`

assuming that prefix`A[:i]`

is sorted by repeated swaps - Example:
$[8,2,4,9,3],[2,8,4,9,3],[2,4,8,9,3],[2,4,8,9,3],[2,3,4,8,9]$

`xxxxxxxxxx`

`def insertion_sort(A, i=None):`

` """Sort A[:i+1]"""`

` if i is None: i = len(A) - 1`

` if i > 0:`

` insertion_sort(A, i-1)`

` insert_last(A, i)`

` `

`def insert_last(A, i):`

` """Sort A[:i+1] assuming sorted A[:i]"""`

` if i > 0 and A[i] < A[i-1]:`

` A[i], A[i-1] = A[i-1], A[i]`

` insert_last(A, i-1)`

`insert_last`

analysis:- Base case: for
, array has one element so is sorted$i=0$ - Induction: assume correct for
, if$i$ , array is sorted; otherwise, swapping last two elements allows us to sort$A[i]>=A[i-1]$ `A[:i]`

by induction. □ $S(1)=\Theta (1);S(n)=S(n-1)+\Theta (1)=\Rightarrow S(n)=\Theta (n)$

- Base case: for
`insertion_sort`

analysis:- Base case: for
, array has one element so is sorted$i=0$ - Induction: assume correct for
, algorithm sorts$i$ `A[:i]`

by induction, and then insert last correctly sorts the rest as proved above. □ $T(1)=\Theta (1);T(n)=T(n-1)+\Theta (n)=\Rightarrow T(n)=\Theta ({n}^{2})$

- Base case: for

- Recursively sort first half and second half (may assume power of two)
- Merge sorted halves into one sorted list (two finger algorithm)
- Example:
$[7,1,5,6,2,4,9,3],[1,7,5,6,2,4,3,9],[1,5,6,7,2,3,4,9],[1,2,3,4,5,6,7,9]$

`xxxxxxxxxx`

`def merge_sort(A, lo=0, hi=None):`

` """Sort A[lo:hi]"""`

` if hi is None: hi = len(A)`

` if hi - lo > 1:`

` mid = (lo + hi + 1) // 2`

` merge_sort(A, lo, mid)`

` merge_sort(A, mid, hi)`

` left, right = A[lo:mid], A[mid:hi]`

` merge(left, right, A, len(left), len(right), lo, hi)`

` `

`def merge(left, right, A, i, j, lo, hi):`

` """Merge sorted left[:i] anr right[:j] into A[lo:hi]"""`

` if lo < hi:`

` if (j <= 0) or (i > 0 and left[i-1] > right[j-1]):`

` A[hi-1] = left[i-1]`

` i -= 1`

` else:`

` A[hi-1] = right[j-1]`

` j -= 1`

` merge(left, right, A, i, j, lo, hi -1)`

`merge`

analysis:- Base case: for
, arrays are empty, so vacuously correct$n=0$ - Induction: assume correct for
, item in$n$ `A[r]`

must be a largest number from remaining prefixes of`left`

and`right`

, and since they are sorted, taking largest of last items suffices; remainder is merged by induction. □ $S(0)=\Theta (1);S(n)=S(n-1)+\Theta (1)=\Rightarrow S(n)=\Theta (n)$

- Base case: for
`merge_sort`

analysis:Base case: for

, array has one element so is sorted$n=1$ Induction: assume correct for

, algorithm sorts smaller halves by induction, and then merge merges into a sorted array as proved above. □$k<n$ $T(1)=\Theta (1);T(n)=2T(n/2)+\Theta (n)$ Substitution: Guess

$T(n)=\Theta (nlogn)$ $cnlogn=\Theta (n)+2c(n/2)log(n/2)=\Rightarrow cnlog(2)=\Theta (n)$ Recurrence Tree: complete binary tree with depth

and$log2n$ leaves, level$n$ has$i$ nodes with${2}^{i}$ work each, total:$O(n/{2}^{i})$ ${\mathrm{\Sigma}}_{i=0}^{lo{g}_{2}^{n}}(2i)(n/{2}^{i})={\mathrm{\Sigma}}_{i=0}^{lo{g}_{2}^{n}}n=\Theta (nlogn)$

- The Master Theorem provides a way to solve recurrence relations in which recursive calls decrease problem size by a constant factor.
- Given a recurrence relation of the form
and$T(n)=aT(n/b)+f(n)$ , with branching factor$T(1)=\Theta (1)$ , problem size reduction factor$a\ge 1$ , and asymptotically non-negative function$b>1$ , the Master Theorem gives the solution to the recurrence by comparing$f(n)$ to$f(n)$ , the number of leaves at the bottom of the recursion tree.${a}^{lo{g}_{b}^{n}}={n}^{lo{g}_{b}^{a}}$ - When
grows asymptotically faster than$f(n)$ , the work done at each level decreases geometrically so the work at the root dominates;$n$ - alternatively, when
grows slower, the work done at each level increases geometrically and the work at the leaves dominates.$f(n)$ - When their growth rates are comparable, the work is evenly spread over the tree’s
levels.$O(logn)$

case | solution | conditions |
---|---|---|

1 | ||

2 | ||

3 | and |

- The Master Theorem takes on a simpler form when f(n) is a polynomial, such that the recurrence has the from
for some constant$T(n)=aT(n/b)+\Theta ({n}^{c})$ .$c\ge 0$

case | solution | conditions | intuition |
---|---|---|---|

1 | Work done at leaves dominates | ||

2 | Work balanced across the tree | ||

3 | Work done at root dominates |

- This special case is straight-forward to prove by substitution (this can be done in recitation).
- To apply the Master Theorem (or this simpler special case), you should state which case applies, and show that your recurrence relation satisfies all conditions required by the relevant case.
- There are even stronger (more general) formulas to solve recurrences, but we will not use them in this class.

- In this model, assume algorithm can only differentiate items via comparisons
**Comparable items**: black boxes only supporting comparisons between pairs- Comparisons are
, outputs are binary: True or False$<,\le ,>,\ge ,=,\ne $ - Goal: Store a set of n comparable items, support find(k) operation
- Running time is
**lower bounded**by # comparisons performed, so count comparisons!

- Any algorithm can be viewed as a
**decision tree**of operations performed - An internal node represents a
**binary comparison**, branching either True or False - For a comparison algorithm, the decision tree is binary (draw example)
- A leaf represents algorithm termination, resulting in an algorithm
**output** - A
**root-to-leaf**path represents an**execution of the algorithm**on some input - Need at least one leaf for each
**algorithm output**, so search requires leaves$\ge n+1$

- What is worst-case running time of a comparison search algorithm?
- running time
# comparisons$\ge $ max length of any root-to-leaf path$\ge $ height of tree$\ge $ - What is minimum height of any binary tree on
nodes?$\ge n$ - Minimum height when binary tree is complete (all rows full except last)
, so running time of any comparison sort is$Height\ge \lceil lg(n+1)\rceil -1=\Omega (logn)$ S$\Omega (logn)$ - Sorted arrays achieve this bound! Yay!
- More generally, height of tree with
leaves and max branching factor$\Theta (n)$ is$b$ $\Omega (logbn)$ - To get faster, need an operation that allows super-constant
branching factor. How??$\omega (1)$

- Exploit Word-RAM
time random access indexing! Linear branching factor!$O(1)$ **Idea!**Give item unique integer key k in , store item in an array at index$\{0,...,u-1\}$ $k$ - Associate a meaning with each index of array.
- If keys fit in a machine word, i.e.
, worst-case$u\le {2}^{w}$ find/dynamic operations! Yay!$O(1)$ - 6.006: assume input numbers/strings fit in a word, unless length explicitly parameterized
- Anything in computer memory is a binary integer, or use (static) 64-bit address in memory
- But space
, so really bad if$O(u)$ ... :($n\ll u$ **Example**: if keys are ten-letter names, for one bit per name, requires TB space${26}^{10}\approx 17.6$ - How can we use less space?

**Idea!**If , map keys to a smaller range$n\ll u$ and use smaller direct access array$m=\Theta (n)$ **Hash function**: (also hash map)$h(k):\{0,...,u-1\}\to \{0,...,m-1\}$ Direct access array called

**hash table**, called the hash of key k$h(k)$ If

, no hash function is injective by pigeonhole principle$m\ll u$ Always exists keys

such that$a,b$ $h(a)=h(b)$ Collision! :($\to $ Can’t store both items at same index, so where to store? Either:

store somewhere else in the array (

**open addressing**)- complicated analysis, but common and practical

store in another data structure supporting dynamic set interface (

**chaining**)

**Idea**! Store collisions in another data structure (a chain)- If keys roughly evenly distributed over indices, chain size is
$n/m=n/\Omega (n)=O(1)!$ - If chain has
size, all operations take$O(1)$ time! Yay!$O(1)$ - If not, many items may map to same location, e.g.
, chain size is$h(k)=constant$ :($\Theta (n)$ - Need good hash function! So what’s a good hash function?

- Heuristic, good when keys are uniformly distributed!
should avoid symmetries of the stored keys$m$ - Large primes far from powers of 2 and 10 can be reasonable
- Python uses a version of this with some additional mixing
- If
, every hash function will have some input set that will a create$u\ll n$ size chain$O(n)$ **Idea**! Don’t use a fixed hash function! Choose one randomly (but carefully)!

- Hash Family
$\mathcal{H}(p,m)=\{{h}_{ab}|a,b\in \{0,...,p-1\}anda\ne 0\}$ - Parameterized by a fixed prime
, with$p>u$ and$a$ chosen from range$b$ $\{0,...,p-1\}$ is a$\mathcal{H}$ **Universal**family:$\underset{h\in \mathcal{H}}{Pr}\{h({k}_{i})=h({k}_{j})\}\le 1/m{\textstyle \phantom{\rule{2em}{0ex}}}\mathrm{\forall}{k}_{i}\ne {k}_{j}\in \{0,...,u-1\}$ - Why is universality useful? Implies short chain lengths! (in expectation)
indicator random variable over${X}_{ij}$ $h\in \mathcal{H}:\text{}{X}_{ij}=1\text{}if\text{}h({k}_{i})=h({k}_{j}),{X}_{ij}=0\text{}otherwise$ - Size of chain at index
is random variable$h({k}_{i})$ ${X}_{i}={\mathrm{\Sigma}}_{j}{X}_{ij}$ - Expected size of chain at index
:$h({k}_{i})$

- Since
, load factor$m=\Omega (n)$ , so$\alpha =n/m=O(1)$ in expectation!$O(1)$

- If
far from 1, rebuild with new randomly chosen hash function for new size m$n/m$ - Same analysis as dynamic arrays, cost can be
**amortized**over many dynamic operations - So a hash table can implement dynamic set operations in expected amortized O(1) time! :)

Data Structure | API Type | Worst Case | |||
---|---|---|---|---|---|

Set | Container | Static | Dynamic | ||

API | `build(x)` | `find(k)` | `insert(k)` `delete(k)` | `find_min()` `find_max()` | `find_prev(k)` `find_next(k)` |

Array | |||||

Sorted Array |