Shreyas’ Notes

Algorithmic Thinking

COMP 182

spring, freshman year

Logic and Proofs §

Propositions §

please don’t confuse AND/conjunction/\wedge with OR/disjunction/\vee.

pp qq pqp \wedge q pqp \vee q pqp \oplus q pqp \rightarrow q qpq \rightarrow p pqp \leftrightarrow q ¬p\neg p ¬q\neg q
F F F F F T T T T T
F T F T T T F F T F
T F F T T F T F F T
T T T T F T T T F F

Tautology: always true

Contradiction: always false

Satisfiable: not a contradiction. not always false. not impossible.

SAT: propositional satisfiability. NP-complete.

Propositional equivalence §

pp and qq are logically equivalent if pqp \leftrightarrow q (p=qp = q) is a tautology.

De Morgan’s laws:

prove equivalences using:

Predicates and Quantifiers §

variables.

e.g. x{1,2,3}x \in \{1, 2, 3\}, P(x):=x{1,2,3}P(x) := x \in \{1, 2, 3\}

quantifiers:

demorgan’s laws:

xyyx\forall x \forall y \equiv \forall y \forall x, xyyx\exists x \exists y \equiv \exists y \exists x

xy≢yx\forall x \exists y \not \equiv \exists y \forall x

negating nested quantifiers:

  1. s/\exists/\forall/g
  2. s/\forall/\exists/g
  3. negate the proposition

Proofs and Proof Techniques §

proofs: valid arguments that establish the truth of statements

Rules of Inference §

Proof techniques §

Sets §

unordered collection of unique items

cardinality of a finite set: number of elements in the set

infinite sets: countable, uncountable

x(xAxB)AB\forall x(x \in A \rightarrow x \in B) \rightarrow A \subseteq B

P(A)=2A={x:xA}\mathscr{P}(A) = 2^A = \{x : x \subseteq A\}

P()={}\mathscr{P}(\varnothing) = \{\varnothing\}

Proper subsets (\subset): subsets excluding the set itself

Set operations §

Set identities §

Functions §

non-empty sets DD (domain) and RR (codomain)

function: assignment — from every element in DD to exactly one element in RR

range (elements actually used as values) \subseteq codomain

f:ABf: A \rightarrow B and f:CDf: C \rightarrow D are equal functions when:

when f:ARf: A \rightarrow \mathbb{R} and g:ARg: A \rightarrow \mathbb{R}

Injections, surjections, bijections §

Inverse and composition §

Relations and their properties §

a binary relation from AA to BB is a subset of A×BA \times B.

(a,b)R(a, b) \in R, aRbaRb

(a,b)∉R(a, b) \not \in R, aba \not R b

composing — aRbbSc    a(RS)caRb \wedge bSc \implies a(R \circ S)c

Representing relations §

Relation closures §

"SS is the closure of RR wrt PP" — relation SS is the smallest set that satisfies property PP such that RSR \subseteq S

[RR is a relation on set AA]:

Equivalence relations §

two elements are equivalent (aba \sim b) if they’re related by an equivalent relation.

RR is an equivalence relation on AA, aAa \in A. equivalence class of aa ([a][a]) is {bA:(a,b)R}\{b \in A: (a,b) \in R\}

partition of AA.

bipartition: n=2n = 2.

fundamental theorem of equivalence relations: the set of all equivalence classes of a relation RR on AA form a partition of AA.

Partial Orders §

set AA + partial order RR = partial-ordered set aka “poset” (A,R)(A, R)

aa and bb are elements of a poset (A,)(A, \preceq)aa and bb are comparable if either aba \preceq b or bab \preceq a. else, they are incomparable.

if (A,)(A, \preceq) is a poset where every two elements of AA are comparable, AA is a totally ordered set and \preceq is a total order.

Hasse diagrams are graphical reps of partial orders. excludes reflexivity and arrows that can be obtained by transitivty.

aa is a maximal element if there’s no cA,cac \in A, c \neq a such that aca \preceq c

bb is a minimal element if there’s no cA,cbc \in A, c \neq b such that cbc \preceq b

minimal and maximal elements do not have to exist or be unique.

aa is the greatest element if cA,ca\forall c \in A, c \preceq a.

bb is the least element if cA,bc\forall c \in A, b \preceq c.

greatest and least elements do not have to exist, but they must be unique.

a totally ordered set (A,)(A, \preceq) is a well-ordered set if every non-empty subset of AA has a least element

Matrices §

Graphs §

Undirected graphs §

Pair (V,E)(V, E) where:

Directed graphs §

aka digraphs

Pair (V,E)(V, E) where:

Jargon §

Special graphs §

Connectivity §

Graph Isomorphism §

Q: subgraph isomorphism vs subgraph

Representing graphs §

n:=n := number of nodes

m:=m := number of edges

Sequences and Summations §

sequence: a function from a subset of the set of integers to a set SS. ana_n, {an}\{a_n\}

recurrence relation for a sequence is an equation that expresses ana_n in terms of one or more of the previous terms of the sequence

summation:

series: sum of a sequence from n=0n = 0 or n=1n = 1 as necessary

Algorithm Efficiency §

finite sequence of precise instructions for performing a computation

Big O notation §

f(x)=O(g(x))f(x) = \mathcal{O}\left(g(x)\right) if there exist positive constants CC and kk such that f(x)Cg(x)f(x) \leq Cg(x) for all xkx \geq k

Big Omega notation §

f(x)=Ω(g(x))f(x) = \Omega\left(g(x)\right) if there exist positive constants CC and kk such that f(x)Cg(x)f(x) \geq Cg(x) for all xkx \geq k

f(x)=Ω(g(x))g(x)=O(f(x))f(x) = \Omega(g(x)) \Leftrightarrow g(x) = \mathcal{O}(f(x))

Big Theta notation §

… aka “order of”

f(x)=Θ(g(x))f(x) = \Theta\left(g(x)\right) if there exist positive constants C1C_1, C2C_2, and kk such that C1g(x)f(x)C2g(x)C_1 g(x) \leq f(x) \leq C_2 g(x) for all xkx \geq k

f(x)=Θ(g(x))f(x) = \Theta(g(x)) iff f(x)=O(g(x))f(x) = \mathcal{O}(g(x)) and f(x)=Ω(g(x))f(x) = \Omega(g(x)).

Complexity of algorithms §

efficiency:

ignore multiplicative and additive constants

for a given input size nn:

if there exists a polynomial-time worst-case algorithm for a problem, the problem is tractable. else, it’s intractable.

halting problem:

post correspondence problem

Asymptoticities of General Functions §

f(x)=O(g(x))f(x) = \mathcal{O}(g(x)) iff k,C\exists k, C such that f(x)Cg(x)|f(x)| \leq C \cdot |g(x)| for all xkx \geq k.

e.g. x=O(x2)-x = \mathcal{O}(-x^2)

Equality and Equivalence §

f(x)=O(g)f(x) = \mathcal{O(g)}” is notation abuse.

O(g)={h:C,k,xk,h(x)Cg(x)}\mathcal{O}(g) = \{h : \exists C, k, \forall x \geq k, h(x) \leq C \cdot g(x)\}

f(x)O(g)f(x) \in \mathcal{O(g)}

Asymptotic equivalence (Θ\Theta) is an equivalence relation.

Helpful results §

f(x)=O(g(x))g(x)=Ω(f(x))f(x) = \mathcal{O}(g(x)) \leftrightarrow g(x) = \Omega(f(x))

f(x)=Θ(g(x))[f(x)=O(g(x))f(x)=Ω(g(x))]f(x) = \Theta(g(x)) \leftrightarrow [f(x) = \mathcal{O}(g(x)) \wedge f(x) = \Omega(g(x))]

Let f(x)=anxn+an1xn1++a1x+a0f(x) = a_n x^n + a_{n - 1} x^{n - 1} + \cdots + a_1 x + a_0 where a0,a1,,anRa_0, a_1, \ldots, a_n \in \mathbb{R}. Then, f(x)=O(xn)f(x) = \mathcal{O}(x^n).

Let f1=O(g)f_1 = \mathcal{O}(g) and f2=O(h)f_2 = \mathcal{O}(h). Then, (f1+f2)=O(max(g,h))(f_1 + f_2) = \mathcal{O}(\max(g, h)).

Let f1=O(g)f_1 = \mathcal{O}(g) and f2=O(h)f_2 = \mathcal{O}(h). Then, (f1f2)=O(gh)(f_1 \cdot f_2) = \mathcal{O}(g \cdot h).

Limit-based definitions §

If f=O(g)f = \mathcal{O}(g), limxfg<\lim_{x \rightarrow \infty} \frac{f}{g} < \infty.

If f=Ω(g)f = \Omega(g), limxfg>0\lim_{x \rightarrow \infty} \frac{f}{g} > 0.

If f=Θ(g)f = \Theta(g), 0<limxfg<0 < \lim_{x \rightarrow \infty} \frac{f}{g} < \infty.

Little ones §

f=o(g)f = o(g) iff limxfg=0\lim_{x \rightarrow \infty} \frac{f}{g} = 0.

f=ω(g)f = \omega(g) iff limxfg=\lim_{x \rightarrow \infty} \frac{f}{g} = \infty.

Asymptotic analogies to relational operators §

Relational operator Analogous asymptotic operator
\leq O\mathcal{O}
\geq Ω\Omega
== Θ\Theta
<< oo
>> ω\omega

BFS §

[see also: COMP 140’s BFS section]

[see also: COMP 140’s Queue section]

Divide-Concur and Recurrences §

Merge sort §

MergeSort\mathrm{MergeSort}:

if n > 1
    copy L[0 .. n/2 - 1] to A
    copy L[n/2 .. n] to B
    MergeSort(A)
    MergeSort(B)
    Merge(A, B, L)

Merge\mathrm{Merge}:

i = 0, j = 0, k = 0

while i < p and j < q
    if A[i] <= B[j]
        L[k] = A[i]
        i++
    else
        L[k] = B[j]
        j++
    k++

if i = p
    copy B[j .. q-1] to L[k .. p+q-1]
else
    copy A[i .. p-1] to L[k .. p+q-1]

Running time T(n)=2T(n2)+O(n)T(n) = 2 T\left(\frac{n}{2}\right) + \mathcal{O}(n).

Master theorem: Let ff be an increasing function such that f(n)=af(nb)+cndf(n) = a f\left(\frac{n}{b}\right) + cn^d. Then:

f(n)={O(nd)a<bdO(ndlogn)a=bdO(nlogba)a>bdf(n) = \begin{cases} \mathcal{O}\left(n^d\right) & a < b^d \\ \mathcal{O}\left(n^d \log n\right) & a = b^d \\ \mathcal{O}\left(n^{\log_b a}\right) & a > b^d \end{cases}

From the master theorem T(n)=O(nlogn)T(n) = \mathcal{O}(n \log n).

T(n)=T(n2)+O(1)=O(logn)T(n) = T\left(\frac{n}{2}\right) + \mathcal{O}(1) = \mathcal{O}(\log n)

Mathematical Induction §

[P(1)k(P(k)P(k+1))]nP(n)[P(1) \wedge \forall k (P(k) \rightarrow P(k + 1))] \rightarrow \forall n P(n)

Important fact: The set of positive integers is well-ordered.

  1. Basis step: Show that P(1)P(1)

  2. Inductive step: Show that kP(k)P(k+1)\forall k P(k) \rightarrow P(k + 1)

    The assumption that P(k)P(k) is called the inductive hypothesis

Strong Mathematical Induction §

  1. Basis step: Show that P(1)P(1)

  2. Inductive step: Show that k[P(1)P(2)P(k)]P(k+1)\forall k [P(1) \wedge P(2) \wedge \cdots \wedge P(k)] \rightarrow P(k + 1)

Recursive definitions §

Σ={0,1}    Σ={ϵ,0,1,00,01,10,11,000,}\Sigma = \{0, 1\} \implies \Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, \ldots\}

ϵ\epsilon: empty string

Exclusion rule

Weighted graphs and greedy algorithms §

Optimization problems and greedy algorithms §

Optimization problem: maximing or minimizing something.

Greedy algorithm:

don’t work for many problems.

Minimum Spanning Tree §

input: weighted graph

output: tree such that the sum of the edges in the tree — eTweighte\sum_{e \in T} weight_e — is minimum

Prim’s algorithm:

Single Source Shortest Paths problem §

input: weighted graph g=(V,E,w)g = (V, E, w) such that w(e)0eEw(e) \geq 0 \forall e \in E; a source node iVi \in V.

output: distance from ii to each node jVj \in V, dJd_J; a shortest path from ii to jj, pjp_j.

Dijkstra’s algorithm:

O(mlogn)\mathcal{O}(m \log n) assuming that the graph is represented as an adj. list and that XX is represented as a min-heap.

Counting §

Pigeonhole principle §

nn holes, n+1n + 1 pigeons; at least one of the pigeonholes has two pigeons.

f:ABf: A \rightarrow B. B<A    a1,a2A:a1a2f(a1)=f(a2)|B| < |A| \implies \exists a_1, a_2 \in A : a_1 \neq a_2 \wedge f(a_1) = f(a_2).

f:XYf: X \rightarrow Y. Y<X    yY:{x:f(x)=y}XY|Y| < |X| \implies \exists y \in Y : |\{x : f(x) = y\}| \geq \lceil\frac{|X|}{|Y|}\rceil

Product and division rules §

Product rule: if A=A1×A2××AnA = A_1 \times A_2 \times \cdots \times A_n, then A=A1×A2××An|A| = |A_1| \times |A_2| \times \cdots \times |A_n|

Division rule.

Sum and subtraction rules §

Sum rule §

A=A1A2AnA = A_1 \cup A_2 \cup \cdots \cup A_n where A1,A2,A_1, A_2, \ldots are pairwise disjoint. A=Ai|A| = \sum |A_i|.

Difference rule §

A=A1A2A = A_1 \cup A_2. A=A1+A2AB|A| = |A_1| + |A_2| - |A \cap B|.

Permutations and Combinations §

Without repetition §

Permutations: Order matters.

0rn0 \leq r \leq n. P(n,r)=n!(nr)!P(n, r) = \frac{n!}{(n - r)!}

Combinations: Order doesn’t matter.

0rn0 \leq r \leq n. C(n,r)=nCr=(nr)=n!r!(nr)!C(n, r) = ^nC_r = \binom{n}{r} = \frac{n!}{r!(n - r)!}

C(n,r)=P(n,r)r!C(n, r) = \frac{P(n, r)}{r!}

With repetition §

the number of kk-permutations of nn items with repetition: nkn^k

the number of kk-combinations of nn items with repetition: (n+k1k)=(n+k1n1)\binom{n + k - 1}{k} = \binom{n + k - 1}{n - 1}

(aka. the number of ways to choose a subset of size kk from a set of size nn)

Inclusion-Exclusion principle §

i=1nAi=i=1nAi1ijnAiAj+1ijknAiAjAk+(1)nA1A2An\left|\bigcup_{i = 1}^n A_i\right| = \sum_{i = 1}^n |A_i| - \sum_{1 \leq i \leq j \leq n} |A_i \cap A_j| + \sum_{1 \leq i \leq j \leq k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^n |A_1 \cap A_2 \cap \cdots \cap A_n|

i=1nAi=k=1n(1)k+1(1i1<<iknAi1Aik)\left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^n (-1)^{k+1} \left( \sum_{1 \leqslant i_1 < \cdots < i_k \leqslant n} | A_{i_1} \cap \cdots \cap A_{i_k} | \right)


f:ABf: A \rightarrow B; A=m|A| = m, B=n|B| = n

Binomial coefficients §

(x+y)n=i=0n(ni)xniyi\left(x + y\right)^n = \sum_{i = 0}^n \binom{n}{i} x^{n - i} y^i

Combinatorial Proofs §

pascal’s identity: (nk)=(n1k1)+(n1k)\binom{n}{k} = \binom{n - 1}{k - 1} + \binom{n - 1}{k}

vandermonde’s identity: (m+nk)=l=0k(mkl)(nl)\binom{m + n}{k} = \sum_{l = 0}^{k} \binom{m}{k - l} \binom{n}{l}

Disscrete Probability §

Experiment, Sample Space, and Event §

Assigning probability §

Given a sample space SS, a probability distribution is a function p:S[0,1]p : S \rightarrow [0, 1] such that sSp(s)=1\sum_{s \in S} p(s) = 1.

uniform distribution: sS,p(s)=1S\forall s \in S, p(s) = \frac{1}{|S|}

Conditional Probability and Independence §

P(EF)=P(EF)P(F)P(E|F) = \frac{P(E \cap F)}{P(F)} (P(F)0P(F) \neq 0)

If P(EF)=P(E)P(E|F) = P(E), EE is independent of FF

P(EF)=P(E)P(F)    P(E \cap F) = P(E) \cdot P(F) \implies EE is independent of FF

P(EF)=P(FE)P(E)P(F)P(E|F) = \frac{P(F|E) P(E)}{P(F)} where P(F)0P(F) \neq 0.

Bayes theorem §

P(DT)=P(TD)P(D)P(TD)P(D)+P(TD)P(D)P(D|T) = \frac{P(T|D) P(D)}{P(T|D) P(D) + P(T|D') P(D')}

If F1,F2,,FnF_1, F_2, \ldots, F_n is a partition of SS,

P(FiE)=P(EFi)P(Fi)i=1n[P(EFi)P(Fi)]P(F_i | E) = \frac{P(E|F_i)P(F_i)}{\sum_{i = 1}^n [P(E|F_i) P(F_i)]}

Bayesian inference: P(MD)P(DM)P(M)P(M|D) \propto P(D|M) P(M)

Random variables §

A random variable is a function from the sample space to the set R\mathbb{R}.

Expected values §

The expectation of a rv XX is its mean.

E(X)=sSp(s)X(s)=xp(x)x\mathbb{E}(X) = \sum_{s \in S} p(s) \cdot X(s) = \sum_x p(x) \cdot x

Linearity of expectations

If X1,X2,,XnX_1, X_2, \ldots, X_n are rv’s on SS, then E(X1+X2++Xn)=E(X1)+E(X2)++E(Xn)\mathbb{E}(X_1 + X_2 + \ldots + X_n) = \mathbb{E}(X_1) + \mathbb{E}(X_2) + \cdots + \mathbb{E}(X_n)

E(aX+b)=aE(X)+b\mathbb{E}(aX + b) = a\mathbb{E}(X) + b

For independent random variables XX and YY, E(XY)=E(X)E(Y)\mathbb{E}(XY) = \mathbb{E}(X)\mathbb{E}(Y).

Variance §

var(X)=x(xE)2p(x)var(X) = \sum_x \left(x - \mathbb{E}\right)^2 - p(x)

var(X)=E[(XE)2]var(X) = \mathbb{E}[\left(X - \mathbb{E}\right)^2]

var(X)=E(X2)[E(X)]2var(X) = \mathbb{E}(X^2) - \left[\mathbb{E}(X)\right]^2

Discrete Probability §

Tail Bounds §

Markov’s inequality: P(xa)E(x)aP(x \geq a) \leq \frac{\mathbb{E}(x)}{a}

P(xaE(x))1aP(x \geq a \mathbb{E}(x)) \leq \frac{1}{a}

Chebyshev’s inequality: P(XE(x)a)V(x)a2P(|X - \mathbb{E}(x)| \geq a) \leq \frac{V(x)}{a^2}

P(xE(x)aσ)1a2P(|x - \mathbb{E}(x)| \geq a \sigma) \leq \frac{1}{a^2}

Families of Distributions §

Bernoulli Distribution §

X={0,1}X = \{0, 1\}

E(X)=xxp(x)=0(1p)+1p=p\mathbb{E}(X) = \sum_x x p(x) = 0 \cdot (1 - p) + 1 \cdot p = p

V(x)=x(xp)2p(x)=p(1p)V(x) = \sum_x {(x - p)}^2 p(x) = p(1 - p)

P(x)={px=11px=0P(x) = \begin{cases}p & x = 1 \\ 1 - p & x = 0\end{cases}

Binomial Distribution §

Run nn independent Bernoulli trials and count the number of successes in the sequence.

p(X=k)=(nk)pk(1p)nkp(X = k) = \binom{n}{k} p^k {(1 - p)}^{n - k}

E(X)=np\mathbb{E}(X) = np

V(X)=np(1p)V(X) = np(1 - p)

Geometric Distribution §

p(X=k)=(1p)k1pp(X = k) = {(1 - p)}^{k - 1} p

E(X)=1p\mathbb{E}(X) = \frac{1}{p}

V(X)=1pp2V(X) = \frac{1 - p}{p^2}

Negative Binomial Distribution §

ll trials until we see kk successes

p(X=l)=(l1k1)(1p)lkpkp(X = l) = \binom{l - 1}{k - 1} {(1 - p)}^{l - k} p^k

Poisson Distribution §

Markov Chains and Hidden Markov Models (HMMs) §

Parameter Estimation For Markov Chains §

Dynamic Programming §

Binomial Coefficients §

Use pascal’s identity and a 2D array similar to a tilted pascal’s triangle.

Longest Increasing Subsequence §

Input: an array of integers

Output: longest possible sequence of indices such that the values indexed by the indices are strictly increasing

Weighted Compatible Intervals §

All pairs shortest paths §

Longest common subsequence §

RNA Secondary Structure Prediction §

Knapsack Problem §

Viterbi’s algorithm §

v[l,i]=maxlQ(v[l,i1]Al,l)×El(xi)v[l, i] = \max_{l' \in Q} (v[l', i - 1] \cdot A_{l', l}) \times E_l(x_i)

for i in 1..L-1:
    for l in Q: # Q is the set of states
        v[l][i] = (max of (v[l_][i - 1] * A[l_][l]) over l_ in Q) * E[l][x_i]

Recurrences §

Modelling with recurrence relations §

examples:

Linear Homogeneous recurrences §

a linear homogeneous recurrence relation of degree kk with constant coefficients is a recurrence relation of the form an=c1an1+c2an2++ckanka_n = c_1 a_{n - 1} + c_2 a_{n - 2} + \cdots + c_k a_{n - k} where c1,c2,,ckRc_1, c_2, \ldots, c_k \in \mathbb{R} and ck0c_k \neq 0.

Infinite Sets and Their Cardinalities §

Infinity and Hilbert’s Grand Hotel §

Hotel with infinite number of (numbered) rooms.

  1. Hotel is full. A new guest shows up.

    Move every guest in room ii to room i+1i + 1, assign room 1 to the new guest.

    Bijection f:{1,2,3,}{2,3,4,}f : \{1, 2, 3, \ldots\} \rightarrow \{2, 3, 4, \ldots\}.

    If XX is finite, there does not exist a bijection f : X \righarrow Y where YXY \subset X

  2. Two-floor hotel

    Bijection from {(1,i),(2,i):iN}{1,2,3,}\{(1, i), (2, i) : i \in \mathbb{N}\} \rightarrow \{1, 2, 3, \ldots\}

  3. More floors

  4. Real-numbered hotel to natural-numbered hotel?

    A bijection from RN\mathbb{R} \rightarrow \mathbb{N} does not exist.

The Infinitesimally Small §

Zeno’s dichotomy paradox.

Infinity, Injections, and Bijections §

Set XX is infinite if there exists a bijection f:XYf : X \rightarrow Y where YXY \subset X.

If there exists a bijection from XYX \rightarrow Y, then XX and YY have the same cardinality.

If there exists a 1-1 function f:XYf : X \rightarrow Y, then XY|X| \leq |Y|.

There exists a bijection f:XYf : X \rightarrow Y iff there exists a bijection g:YXg : Y \rightarrow X.

Shröder-Bernstein Theorem: if AA and BB are two sets such that AB|A| \leq |B| and BA|B| \leq |A|, then A=B|A| = |B|. Show a one-to-one function f:ABf : A \rightarrow B and a one-to-one function g:BAg : B \rightarrow A.

An infinity of infinities §

Every finite set is countable.

A infinite set XX is countably infinite if there exists a bijection f:NXf : \mathbb{N} \rightarrow X.

A infinite set XX is uncountable if there doesn’t exist a bijection f:NXf : \mathbb{N} \rightarrow X. Proof: Cantor’s diagonal argument.

Continuum hypothesis: A<2A|A| < |2^A|. 0<1<\aleph_0 < \aleph_1 < \cdots

“Zermelo-Fraenkel axioms of set theory”