CR4-DL

CPSC 413: Design & Analysis of Algorithms I

By Brian Pho

Asymptotics (4)

L01: Introduction to course, asymptotics

Order the following functions in order of increasing asymptotic growth

  • n1/2n^{1/2}
  • 18n3\frac{1}{8}n^{3}
  • n32nn^{3}-2n
  • n2n+7n^{2}-\sqrt{n}+7
  • 12nn12\frac{1}{2}n-n^{\frac{1}{2}}
  • n2n0.6\frac{n^{2}}{n^{0.6}}
  • n3\sqrt{n^{3}}
  • 7n137n-13
  • 8383
  • n3+20\sqrt[3]{n} + 20

One way of comparing algorithms is by comparing their asymptotic growth. Increasing order

  1. 8383
  2. n3+20\sqrt[3]{n} + 20
  3. n1/2n^{1/2}
  4. 7n1312nn127n-13 \equiv \frac{1}{2}n-n^{\frac{1}{2}}
  5. n2n0.6\frac{n^{2}}{n^{0.6}}
  6. n3\sqrt{n^{3}}
  7. n2n+7n^{2}-\sqrt{n}+7
  8. 18n3n32n\frac{1}{8}n^{3} \equiv n^{3}-2n

Theorem: f1(n) ϵ O(g1(n))f_{1}(n)\ \epsilon\ O(g_{1}(n)) Def: O(g)={f:RR  n0>0,c2>0,f1(n)c2g1(n) for all nn0}O(g) = \{f:R \Rightarrow R\ |\ \exists n_{0} > 0, \exists c_{2} > 0, f_{1}(n) \leq c_{2}g_{1}(n)\ for\ all\ n \geq n_{0}\}

  • The purpose of c2c_2 is to say that no matter what value of c2c_{2} is used, f1(n)f_{1}(n) will always be smaller than g1(n)g_{1}(n).
  • c2g1(n)c_{2}g_{1}(n) will always be slower than or equal to f1(n)f_{1}(n) above the threshold of n0n_{0} where n0n_{0} is the intersection between f1(n)f_{1}(n) and g1(n)g_{1}(n); correction: where n0n_{0} is an arbitrarily chosen constant.
  • n0n_{0} and c2c_{2} are correlated.

L02: (Asymp) Asymptotics, big-Oh notation

notion idea interpretation pronunciation
o(g)o(g) << f grows strictly slower than g little-oh
O(g)O(g) \leq f grows no faster than g big-oh
θ(g)\theta(g) == f grows as fast as g theta
Ω(g)\Omega(g) \geq f grows no slower than g big-omega
ω(g)\omega(g) >> f grows strictly faster than g little-omega

Ex: If f1(n)=n2f_{1}(n) = n^{2}, g1(n)=n3g_{1}(n) = n^{3}, then f1(n) ϵ O(g1(n))f_{1}(n)\ \epsilon\ O(g_{1}(n)). Proof: Let n0=1n_{0} = 1 and c2=1c_{2} = 1.

Def: o(g)={f,c2>0,n0>0,0f(n)c2g(n) for all nn0}o(g) = \{f, \forall c_{2}>0, \exists n_{0} > 0, 0 \leq f(n) \leq c_{2}g(n)\ for\ all\ n \geq n_{0}\}.

  • No matter how much we speed up algorithm gg (speed up comes in the form of c2c_{2}), the algorithm ff will always be faster once the input size is big enough (the threshold comes in the form of n0n_{0}.

Ex: If f1(n)=n2f_{1}(n) = n^{2}, g1(n)=n3g_{1}(n) = n^{3}, then f1(n) ϵ o(g1(n))f_{1}(n)\ \epsilon\ o(g_{1}(n)). Proof: Let n0=500n_{0} = 500 and c2=1500c_{2} = \frac{1}{500}, then we want n2c2n3n^{2} \leq c_{2}n^{3}. Given c2c_{2}, set n0=1c2+1n_{0} = \frac{1}{c_{2}} + 1 so there is always a threshold for any given speedup. The plus one is just to guarantee the threshold but it could be any number added.

  • Theta is a combination of big-oh and big-omega; it isn’t faster and isn’t slower, it’s the same.
  • c1c_{1} is the slow down factor, c2c_{2} is the speedup factor.

Properties of big-O

  • f ϵ o(g)f ϵ O(g)f\ \epsilon\ o(g) \Rightarrow f\ \epsilon\ O(g). If ff is strictly slower than gg, then ff is slower (no faster) than gg.
  • f ϵ ω(g)f ϵ Ω(g)f\ \epsilon\ \omega(g) \Rightarrow f\ \epsilon\ \Omega(g).
  • f ϵ O(g) & f ϵ Ω(g)f ϵ Θ(g)f\ \epsilon\ O(g)\ \&\ f\ \epsilon\ \Omega(g) \Leftrightarrow f\ \epsilon\ \Theta(g).
  • f ϵ O(g)g ϵ Ω(f)f\ \epsilon\ O(g) \Leftrightarrow g\ \epsilon\ \Omega(f).
  • f ϵ Θ(g)g ϵ Θ(f)f\ \epsilon\ \Theta(g) \Leftrightarrow g\ \epsilon\ \Theta(f).
  • f ϵ o(g)g ϵ ω(f)f\ \epsilon\ o(g) \Leftrightarrow g\ \epsilon\ \omega(f).

L03: (Asymp) Limit test, logarithms, exponentials

  • Logs come from cutting the search space usually in half hence log2()log_2().
  • We assume all logs have base 2.
  • Theorem: a,b>1,n>0,loga(n)=logb(n)logb(a)\forall a, b > 1, n > 0, log_{a}(n)=\frac{log_{b}(n)}{log_{b}(a)}. Lets you switch the log base.
  • Examples
    • 7log(n) ϵ Θ(log(n))7log(n)\ \epsilon\ \Theta(log(n))
    • (log(n))7 ϵ ω(log(n))(log(n))^{7}\ \epsilon\ \omega(log(n))
    • log(7n)=n log(7) ϵ Θ(n)log(7^{n}) = n\ log(7)\ \epsilon\ \Theta(n)
  • Theorem: a,b>0,limn(log(n))bna=0\forall a, b > 0, \lim_{n\to\infty} \frac{(log(n))^{b}}{n^{a}} = 0
    • The intuition is that the top is faster than the bottom.
    • Any log-power is smaller than any polynomial.
  • Examples
    • (log(n))2 ϵ o(n)(log(n))^{2}\ \epsilon\ o(n)
    • (log(n))2 ϵ o(n)(log(n))^{2}\ \epsilon\ o(\sqrt{n})
    • (log(n))7 ϵ o(n1/100)(log(n))^{7}\ \epsilon\ o(n^{1/100})
    • (log(n))2 ϵ o(n(log(n))2)(log(n))^{2}\ \epsilon\ o(\frac{n}{(log(n))^{2}})
  • Ordering example
    • nlog n\frac{n}{log\ n}
    • log nlog\ n
    • n\sqrt n
    • log(log n)log(log\ n)
    • (log n)2(log\ n)^{2}
    • nn
    • log n\sqrt{log\ n}
    • (log n)(log log n)(log\ n)(log\ log\ n)
    • n(log n)2\frac{n}{(log\ n)^{2}}
    • (log n)2n\frac{(log\ n)^{2}}{n} (Not an algorithm)
  • Answer in increasing growth order
    1. (log n)2n\frac{(log\ n)^{2}}{n}
    2. log(log n)log(log\ n)
    3. log n\sqrt{log\ n}
    4. log nlog\ n
    5. (log n)(log log n)(log\ n)(log\ log\ n)
    6. (log n)2(log\ n)^{2}
    7. n\sqrt{n}
    8. n(log n)2\frac{n}{(log\ n)^{2}}
    9. nlog n\frac{n}{log\ n}
    10. nn
  • One helpful tip for ordering algorithms is to cancel the same terms on both sides.
  • Theorem: log(n!) ϵ Θ(n log(n))log(n!)\ \epsilon\ \Theta(n\ log(n))
    • Suppose we have a deck of cards, we want to find some permutation where they’re sorted.
    • The search space is n!n! and applying log()log() to it means we split the search space in half for every iteration.
    • n!nnn! \leq n^{n}, then log both sides to get log(n!)n log(n)log(n!) \leq n\ log(n) which is the big-O bound of the theorem.
    • n!=n(n1)(n2+1)(n2)...1(n2)n2n! = n \cdot (n-1) \cdot (\frac{n}{2} + 1)(\frac{n}{2})...1 \geq (\frac{n}{2})^{\frac{n}{2}}, then log both sides to get log(n!)n2log(n2)log(n!) \geq \frac{n}{2}log(\frac{n}{2}) which is the big-Theta bound of the theorem.

L04: (Asymp) Classification of exponentials, polynomials, and logarithms

  • An algorithm transforms an input into an output by performing some transformation on the input.
  • What is an efficient algorithm?
    • An algorithm that is fast. Doesn’t have to be optimal.
    • An algorithm is efficient if it runs in polynomial time in the input size. (Will show up on final exam)
  • 2n<n!<nn2^{n} < n! < n^{n}
  • Poly logs, subpolys, polys are efficient. Super polys, exps, and superexps aren’t efficient. (For exams, if asked for an efficient algorithm, then it must be in the first three groups).

Greedy (5)

L05: (Greedy) Interval scheduling 1

  • Proof techniques
    • Our greedy algorithm never makes a bad choice.
    • Our greedy algorithm always makes a good choice.
    • Our greedy algorithm stays ahead.
    • Our greedy algorithm is on the way to produce an optimal.
    • At any stage r during the computation subset Ar can be extended to an optimal solution.
  • Pieces of Candy
    • You can pick 4 pieces of candy.
    • We want to maximize the total weight of candy.
    • Greedy heuristic: Always pick the heaviest remaining piece.
  • Greedy algorithms are typically simple and can be stated in one line.
  • Candy pickings
    • Input: Integers n, kn,\ k with 1kn1\leq k\leq n. Weights w1,w2,...,wnw_{1}, w_{2}, ..., w_{n}.
    • Output: Heaviest subset A{1,2,...,n}A \subseteq \{1, 2, ..., n\} of size k. weight(A)=i ϵ Awiweight(A) = \sum_{i\ \epsilon\ A} w_{i}.
    • Theorems
      • Our algorithm produces a valid solution.
      • Our algorithm produces an optimal solution.
      • Our algorithm runs in polynomial time.
    • Proof
      • What we want: Subset ArA_{r} can be extended to an optimal solution for all 0rk0 \leq r \leq k. (If we can proof this then we are done).
      • Proof by contradiction. Assume there is some jj such that AjA_{j} can’t be extended to an optimal solution. Aka assume there’s a state that can’t be extended to an optimal solution.
      • Let r=smallest jr = smallest\ j such that AjA_{j} can’t be extended to an optimal solution.
        • A0={}{9,4,8,10}A_{0} = \{\} \cup \{9, 4, 8, 10\} where {9,4,8,10}\{9, 4, 8, 10\} is an extension that would lead to an optimal solution.
      • A1={9}{4,8,10}A_{1} = \{9\} \cup \{4, 8, 10\}
        • Ar1={a1,a2,...,ar1}{br,br+1,...,bn}A_{r-1} = \{a_{1}, a_{2}, ..., a_{r-1}\} \cup \{b_{r}, b_{r+1}, ..., b_{n}\} where {br,br+1,...,bn}\{b_{r}, b_{r+1}, ..., b_{n}\} is an extension that would lead to an optimal solution.
      • Ar={a1,a2,...,ar1}{ar}A_{r} = \{a_{1}, a_{2}, ..., a_{r-1}\} \cup \{a_{r}\} ← The step where we made a mistake aka we can’t extend to an optimal solution.
        • Fact 1: Arˉ={a1,a2,...,ar1}{ar}{br+1,bk}\bar{A_{r}} = \{a_{1}, a_{2}, ..., a_{r-1}\} \cup \{a_{r}\} \cup \{b_{r+1}, b_{k}\}
          • Observation 1: Arˉ\bar{A_{r}} has size kk so it is a valid set.
        1. The indices {a1,...,ar1,ar}\{a_{1},..., a_{r-1}, a_{r}\} are all distinct because the greedy algorithm picks only distinct indices by definition of our greedy algorithm.
        2. The indices {a1,...,ar1,br+1,...,bk}\{a_{1}, ..., a_{r-1}, b_{r+1}, ..., b_{k}\} are distinct because it’s part of an optimal solution by definition.
        3. The index of ara_{r} is distinct from {br+1,...,bk}\{b_{r+1}, ..., b_{k}\} because had it been one of them, then ArA_{r} could have been extended.
      • Ar1={a1,...,ar1}{br}{br+1,...,bk}A_{r-1}^{*} = \{a_{1}, ..., a_{r-1}\} \cup \{b_{r}\} \cup \{b_{r+1}, ..., b_{k}\} is an optimal solution.
    • Arˉ={a1,...,ar1}{ar}{br+1,...,bk}\bar{A_{r}} = \{a_{1}, ..., a_{r-1}\} \cup \{a_{r}\} \cup \{b_{r+1}, ..., b_{k}\} is our greedy solution.
      • Fact 2: We want to argue value(Arˉ)value(Ar1)value(\bar{A_{r}}) \geq value(A_{r-1}^{*}) by arguing that weight(ar)weight(br)weight(a_{r}) \geq weight(b_{r}).
      • We know that weight(ar)weight(br)weight(a_{r}) \geq weight(b_{r}) because the greedy algorithm picks the heaviest among the remaining pieces.
      • From Fact 1 and Fact 2, we can conclude that Arˉ\bar{A_{r}} is a valid and optimal solution. That is a contradiction to our assumption that ArA_{r} can’t be extended to an optimal solution.
  • Proof by contradiction is the same as proof by induction.

L06: (Greedy) Interval scheduling 2

  • Interval scheduling
    • Input: Set of n jobs. Each job has a starting time sis_{i} and a finishing time fif_{i}.
    • Output: Select as many non-overlapping jobs as possible.
  • Approaches
    • Pick the shortest job of the next available jobs.
    • Pick the next available job / job that starts first.
    • Pick the job that ends the first.
      • Split ties arbitrarily.
      • Among jobs that do not overlap already picked jobs.
  • Answer to handout: {4, 11, 8, 1, 10}
  • A good algorithm
    • Outputs a valid solution.
    • Outputs an optimal solution.
    • Runs in poly time.
  • For the interval scheduling GA
    • By definition of the GA, we will never pick a job that overlaps so the solution is valid.
    • The proof that it gives an optimal solution is given below.
    • The GA is poly time as we can sort the job deadlines in nlog(n)n log(n) time.
    • Proof idea: GA never makes a bad choice (on our way to construct an optimal solution).
    • Theorem: Subset AsA_{s} can be extended to an optimal solution for all 0sk0 \leq s \leq k^{*}.
      • Proof by contradiction.
      • Assume there exists some jj such that AjA_{j} cannot be extended to an optimal solution.
      • Let rr be the smallest jj such that AjA_{j} cannot be extended to an optimal solution. In other words, let rr be the first time we make a mistake.
      • Then Ar1={a1,a2,...,ar1}{br,...}A_{r-1} = \{a_{1}, a_{2}, ..., a_{r-1}\} \cup \{b_{r},...\} can be extended to an optimal solution but Ar={a1,a2,...,ar1}{ar}A_{r} = \{a_{1}, a_{2}, ..., a_{r-1}\} \cup \{a_{r}\} cannot be extended.
      • Let the extension be {br,br+1,...,bk}\{b_{r}, b_{r+1},...,b_{k}\} be an optimal extension.
      • We aren’t going to argue that ArA_{r} is in the optimal extension because there might be multiple optimal solutions.
      • We’re going to argue that ArA_{r} can be extended to an optimal solution to contradict our assumption.
      • Because ArA_{r} is the greedy choice, we know that ara_{r} will end before or at the same time as brb_{r}.
      • Then extend ArA_{r} by {br+1,...,bk}\{b_{r+1}, ..., b_{k}\} but the extension is not necessarily valid because ara_{r} and br+1b_{r+1} could overlap.
      • The solution to this problem is to sort the optimal extension and to replace the earliest job with the greedy choice. Let brb_{r} be the job that finishes the earliest among jobs {br,br+1,...}\{b_{r}, b_{r+1}, ...\}.
      • There’s a greedy choice and that choice can be substituted into an optimal extension.

L07: (Greedy) Shortest paths in graphs

  • Dijkstra’s Greedy Algorithm
    1. For all u ϵ Vu\ \epsilon\ V, set d(u)=d(u) = \infty. Set S0={s}S_{0}=\{s\}, d(s)=0d(s)=0, A0={}A_{0}=\{\}.
    2. For k=1k=1 to n1n-1, do
      1. Find v ϵ V not in Sv\ \epsilon\ V\ not\ in\ S with min{d(u)+l(u,v)}min\{d(u) + l(u,v)\} ← Greedy choice
      2. Set d(v)=d(u)+l(u,v)d(v) = d(u) + l(u,v), Sk=Sk1{v}S_{k}=S_{k-1} \cup \{v\}, Ak=Ak1{(u,v)}A_{k} = A_{k-1} \cup \{(u,v)\}
  • Single source shortest path problem
    • Input: Directed graph G=(V,E)G=(V,E), connected source s ϵ Vs\ \epsilon\ V. Non-negative weights for each edge.
    • Goal: A shortest path from s to every other vertex v ϵ Vv\ \epsilon\ V.
  • Solution is a tree rooted at s.
  • GA is to grow a shortest-path tree.
  • The proof depends on choosing paths that we will never regret.
  • Proof
    • We only pick edges that we’ll never regret.

L08: (Greedy) Minimum spanning tree

  • Kruskal algorithm
    1. Presort edges e1,e2,...,eme_{1}, e_{2},...,e_{m} so that c(e1)c(e2)c(em)c(e_{1}) \leq c(e_{2}) \leq c(e_{m}) where c(...)c(...) is the cost of the edge.
    2. Fo={}F_{o} = \{\}, k=0k=0
    3. For i = 1 to m
      1. If Fk{ei}F_{k} \cup \{e_{i}\} is acyclic then Fk+1=Fk{ei}F_{k+1} = F_{k} \cup \{e_{i}\} and k=k+1k=k+1.
    4. Return FkF_{k} and kgrk_{gr} where kgr=kk_{gr} = k.
  • Minimum Spanning Tree (MST)
    • Undirected graph with non-negative edge costs.
  • Trees are paths that are unique paths.
  • A spanning tree has n - 1 edges.
  • A tree contains a unique path from every vertex to every other vertex.
  • If we add an edge to a spanning tree, then we introduce a unique cycle.
  • One GA to obtain the MST is to remove the edge with the greatest cost without making the graph disconnected.
  • Kruskal’s Heuristic
    • Pick the cheapest cost edge that doesn’t introduce a cycle.
  • Whenever we have a cycle, we can remove the edge with the most cost.
  • Theorem: Kruskal’s algorithm outputs a MST. (Assume Kruskal’s alg outputs a tree)
    • Proof by contradiction.
    • Assume there is some kk such that FkF_{k} can’t be extended to an optimal solution. Aka Kruskal’s algorithm made a mistake.
    • Let r = smallest such k. So Fr1F_{r-1} can be extended to an optimal solution but FrF_{r} can’t.
    • Let Fr1=Fr1{er,...,en1}F_{r-1}^{*} = F_{r-1} \cup \{e_{r},...,e_{n-1}\} be the optimal solution and Fr=Fr1{ex}F_{r} = F_{r-1} \cup \{e_{x}\} be the set where we made the mistake.
    • Because of the greedy choice, the edge GA picked must be at least the same cost as the optimal solution.
    • So we can extend FrF_{r} to an optimal solution by Frˉ=(Fr1{ex}{ey})\bar{F_{r}} = (F_{r-1} \cup \{e_{x}\} - \{e_{y}\}).

L09: (Greedy) Huffman codes

  • Huffman Codes
    • Input: A set of n symbols. S={s1,s2,sn}S = \{s_{1}, s_{2}, s_{n}\} with frequencies f1,f2,fnf_{1}, f_{2}, f_{n}.
    • Output: An optimal prefix-free code over {0, 1} for those frequencies
  • Example
    • Message (M) = “appletrees”
    • StdEnc(M) = 01.1.1.00.0.000.10.0.0.11 ← Not an accurate encoding because the decimal is a third symbol.
    • Prefix-free code: a code that is unambiguous by having each encoding not have the same prefix.
symbol frequency standard encoding (std enc)
e 3 0
p 2 1
l, a, r, s, t 1 00, 01, 10, 11, 000
  • Observation 1: More frequently used characters should be have a shorter encoding. fi>fjE(si)E(sj)f_{i} > f_{j} \rightarrow \lvert E(s_{i}) \rvert \leq \lvert E(s_{j}) \rvert
  • A prefix-free code is a binary tree.
  • Swap leaves to get higher frequencies closer to the root.
  • If you keep swapping subtrees until no longer possible, then we get an optimal prefix-free code.
  • In practice, the tree is built bottom up.
  • GA means I can locally find an improvement.
  • If it seems that I can make a local improvement, then GA will probably apply.

Divide & conquer (4)

L10: (D&C) Simple recursive algorithms

  • Recurrences
    • Mergesort (Θ(nlog(n))\Theta(nlog(n)))
      • T(2)=1T(2)=1
      • T(n)=2T(n2)+nT(n)=2T(\frac{n}{2})+n
    • Bubblesort (Θ(n2)\Theta(n^{2}))
      • T(1)=0T(1)=0
      • T(n)=T(n1)+nT(n)=T(n-1)+n
    • Binary search (Θ(log(n))\Theta(log(n)))
      • T(1)=1T(1)=1
      • T(n)=T(n2)+1T(n)=T(\frac{n}{2})+1
    • Integer multiplication (Θ(nlog2(3))Θ(n1.57)\Theta(n^{log_{2}(3)}) \approx \Theta(n^{1.57}))
      • T(1)=1T(1)=1
      • T(n)=3T(n2)+1T(n)=3T(\frac{n}{2})+1
  • Multiplication of complex numbers
    • Input: (a + bi)(c + di)
    • Output: (ac - bd) + (bc + ad)i
  • Faster algorithm for multiplying two complex numbers
    • 3 multiplications (1 at r, 1 at s, 1 at t)
    • 5 additions/subtractions (2 at r, 2 at e, 1 at f)
r = (a + b)(c + d) = ac - bd + bc - ad
s = bc
t = ad
e = ac - bd = r - s + t
f = ad + bc = s + t
  • Multiplication of large integers
    • abcdab * cd where a is the upper half of the bit string, b is the lower half of the bit string, and ab is the entire number represented as a bit string.
    • (a2n/2+b)(c2n/2+d)(a \cdot 2^{n/2} + b)(c \cdot 2^{n/2} + d)
    • (ac)2n+(ad+bc)2n/2+bd(ac)2^{n} + (ad + bc)2^{n/2} + bd where 2n2^{n} and 2n/22^{n/2} are shifts.
    • Apply the same trick when multiplying two complex numbers.
    • Requires 3 multiplications, 4 additions, and 2 shifts.
  • When explaining recursion, describe the recursive step, not the entire process. Avoid using iteration to describe recursion. E.g. For all, for each, etc.
  • Matrix multiplication
    • For each entry in the answer matrix, it requires O(n)O(n) operations so constructing the entire answer matrix requires O(n3)O(n^{3}) since nn2=n3n \cdot n^2 = n^3.
    • Recursive method
      • Split each matrix into quadrants.

L11: (D&C) Largest sum of subarray and Recursions

  • Mergesort recurrence: T(n)=2T(n/2)+n+nT(n) = 2T(n/2) + n + n
    • 2T(n/2)2T(n/2) because we split the input in half and we have to sort two subarrays.
    • +n+n+ n + n because we divide the array and later merge it
  • Example
    • [7,3,11,5,4,3,7,2,9,8,12,2][7, 3, -11, 5, 4, -3, 7, 2, -9, -8, 12, -2]
    • Sample output: [5,4,3,7,2]=15[5, 4, -3, 7, 2] = 15.
  • Brute force is Θ(n3)\Theta(n^{3}) because we try all starting indices and all ending indices. Getting the starting and ending indices is n2n^{2} and getting the indices between them is nn.
  • D&C is to split the array into two subarrays and to calculate the largest sum of those subarrays. We also need to care for the case when the solution crosses the border.
  • We ask each subarray for its
    • Largest subarray
    • Largest subarray touching the dividing border
    • Largest subarray touching its edges
    • Total sum
  • Each subarray returns four pieces of information.
  • Whatever I ask my children, I must also give to my parent.
  • The largest sum of an array must come from three cases
    • The left subarray
    • The right subarray
    • A combination of the left and right subarray
  • Runtime of T(n)=2T(n/2)+Θ(n)+Θ(1) ϵ Θ(nlogn)T(n) = 2T(n/2) + \Theta (n) + \Theta(1)\ \epsilon\ \Theta(n log n)
    • Dividing is linear time if we copy the array into two subarrays.
    • Merging is clearly constant time Θ(1)\Theta(1). We need to compute 4 numbers from 8 numbers.
  • T(n)=2T(n/2)+Θ(1)+Θ(1) ϵ Θ(n)T(n) = 2T(n/2) + \Theta (1) + \Theta(1)\ \epsilon\ \Theta(n)
    • If the division were constant time, then the algorithm would be linear. It can be if we pass indices for the start and end of the subarray instead of copying.
  • Master Theorem
    • Let T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n) where aa is the number of subproblems, bb is the size of each subproblem, and f(n)f(n) is the cost of dividing and merging.
    • Depth = logb(n)log_{b}(n).

L12: (D&C) Closest points in the plane

  • Input: n points (x1,y1),...,(xn,yn)(x_{1}, y_{1}), ..., (x_{n}, y_{n})
  • Output: the two closest points
  • {dist(p,p)=xx2+yy2}\{dist(p, p') = \sqrt{|x-x'|^2 + |y-y'|^2}\}
  • Trivial algorithm: Θ(n2)\Theta(n^2)
  • Now: Θ(n log(n))\Theta(n\ log(n))
  • Master theorem
    • Case 1: Many leaves so the cost is mostly the leaves. More expensive to solve subproblems.
    • Case 2: Leaves and root are the same cost. Same to solve subproblems.
    • Case 3: Few leaves so the cost is mostly the root. Cheaper to solve subproblems.
  • To solve for the closest points in a plane
    • Divide the plane into half
    • Find the half by presorting
    • Solve each half recursively and deal with the border somehow
    • Whatever we get as input, our children should get as input
  • Algorithm
    Presort (n log n Time)
      P_x = all n points sorted with respect to x-axis
      P_y = all n points sorted with respect to y-axis
    Divide (Linear Time)
      Q_x = left half of points sorted with respect to x-axis
      Q_y = left half of points sorted with respect to y-axis
      R_x = right half of points sorted with respect to x-axis
      R_y = right half of points sorted with respect to y-axis
    Merge
      d = min(d_left, d_right)
      d_final = min(d_left, d_right, d_border)
  • We want to merge in linear time to get n log n time.
  • Discard all points that are delta (d) away from the border.
  • We use P_y to get the points closer to the border in linear time.

L13: (D&C) FFT - Fast Fourier Transforms

  • D&C = Recursion with non-overlapping
  • DP = Recursion with overlapping subproblems
    • Develop recursively
    • Implement iteratively
  • Don’t use memoization because it doesn’t speak enough about recursion.
  • Master theorem
    • f(n)f(n) is the cost of the root, nlogb(a)n^{log_b(a)} is the cost of the leaves.
    • Master theorem doesn’t apply to non-polynomial separated functions, only to poly-separated functions.

Dynamic programming (5)

L14: (DP) Scheduling

  • Job selection
    • Input: wages w1,w2,...,wnw_1, w_2, ..., w_n (wages for 1 day of work)
    • Output: Earn as much as possible
    • Constraint: You cannot work 2 days in a row
    • Examples
      • E.g. [4,3,2,4,1][4, 3, 2, 4, 1] (n = 5)
      • Work on days 1 and 4 to earn 8.
      • E.g. [6,9,2,1,4,5,3][6, 9, 2, 1, 4, 5, 3] (n = 7)
      • Work on days 2, 5, and 7 to earn 16.
      • E.g. [6,9,2,1,4,5,3,4][6, 9, 2, 1, 4, 5, 3, 4] (n = 8)
      • Work on days 2, 4, 6, and 8 to earn 19.
    • Greedy doesn’t work because we can’t extend the solution from n = 7 to n = 8.
    • A small change at the end changes the solution so this is a global problem.
    • Solution
      • Recursively think about solving the subproblems.
      • Either we work day n or we don’t work day n.
      • If we work day n, then we can’t work day n - 1. Work optimally among the first n - 2 days.
      • If we don’t work day n, then we work optimally among the first n - 1 days.
      • We pick the better of the two conditionals.
    • Proof
      • Base case
        • (n = 1) work day 1
        • (n = 2) work the day with the higher wage
      • The important idea is to ask what is the optimal value from the children.
      • What value do you want from your children?
      • C[k]C[k] = optimal value we can earn among days 1,2,...,k1, 2, ..., k. CORE OF ALGORITHM
    • C[n]=max{wn+C[n2],C[n1]}C[n] = max\{w_n + C[n-2], C[n-1]\}. Either we work for wage wnw_n or we don’t work.
      • C[k]=max{wk+C[k2],C[k1]}C[k] = max\{w_k + C[k-2], C[k-1]\} for k3k \geq 3.
    • C[2]=max{w1,w2}C[2] = max\{w_1, w_2\}
      • C[1]=w1C[1] = w_1
  • Implementation (Bottom-Up)
    • E.g. [6,9,2,1,4,5,3,4][6, 9, 2, 1, 4, 5, 3, 4] (n = 8)
    • Base case: C=[6,9]C = [6, 9]
    • Completed C: C=[6,9,9,10,13,15,16,19]C = [6, 9, 9, 10, 13, 15, 16, 19]
    • Output 19 as the total we will earn.
    • Remember to output a value from your algorithm.
  • Weighted Interval Scheduling
    • We can make a small change to the problem (changing a weight to infinity) that changes the entire solution.
    • Think in terms of the number of jobs (n), not the number of days (d).
    • Solution
      • Presort the intervals with respect to finishing time. (Break ties arbitrarily)
      • Either we work job n and earn wage w
        • Work optimally among jobs that finishes before job n starts.
      • Or we don’t work job n and don’t earn w
        • Work optimally among jobs 1, …, n-1
      • C[n]C[n] = maximum amount we can earn among jobs 1 through n.
    • C[k]C[k] = max amount we can earn among jobs 1 through k (k1k \geq 1)
      • Either we work job n so: wn+maxj{C[j]fjsn}w_n + max_j\{C[j] \vert f_j \leq s_n\} (we want to maximize the wage for jobs that finish before n starts)
      • Or we don’t work job n so: C[n1]C[n-1] (work optimally among n1n-1 jobs)
      • Then we take the max of both cases to get C[n]C[n].
      • C[1]=w1C[1] = w_1 for the base case.

L15: (DP) Knapsack and Subset Sum

  • Our algorithm developed today is not poly-time.
  • Problem
    • Input
      • n items
      • weights w1,w2,...,wnw_1, w_2, ..., w_n
      • values v1,v2,...,vnv_1, v_2, ..., v_n.
      • Knapsack of capacity W
    • Output
      • Fill knapsack with as valuable load as possible (not overfill)
    • Example
      • (w=10, $25), (w=15, $30), (w=20, $80), (w=30, $100)
      • Knapsack of size 45
      • An optimal solution: {1,2,3}\{1, 2, 3\}. The optimal value: $135
    • Solution
      • Either we pick item n
        • The knapsack capacity changes. Remaining capacity is WwnW - w_n where WW is the knapsack capacity before we chose n. If it doesn’t fit then don’t consider it.
        • We earn the the value of n plus the optimal value among 1 to n1n-1.
      • Or we don’t pick item n
        • Earn optimally among items 1 to n1n-1.
        • Remaining capacity doesn’t change.
      • C[n,W]C[n, W] = maximum value in knapsack of capacity WW among items 1 through n.
    • C[k,T]C[k, T] = maximum value in knapsack of capacity TT among items 1 through k.
      • A 2D array where the rows are the number of items and the columns are the capacity of the knapsack.
      • Populating the array takes Θ(nW)\Theta(n \cdot W) which is not poly-time. Poly-time means an algorithm that runs in polynomial time on the input size. It’s actually exponential.
      • C[n,W]=max(C[n1,Wwn]+vn(either case),C[n1,W](or case))C[n, W] = max(C[n-1, W- w_n] + v_n (either\ case), C[n-1,W] (or\ case))
      • C[k,T]=max(C[k1,Twk]+vk(either case),C[k1,T](or case))C[k, T] = max(C[k-1, T-w_k] + v_k (either\ case), C[k-1,T] (or\ case))
      • Base cases
        • 0 capacity = 0 value
        • 0 items = 0 value
    • DP = Recursion

L16: (DP) Word problems

  • Longest common subsequence
    • Input: Two string X and Y of lengths n and m. X=x1,x2,...,xnX = x_1, x_2, ..., x_n and Y=y1,y2,...,ynY = y_1, y_2, ..., y_n.
    • Output: Length of a LCS of X and Y.
    • A subsequence, Z, of a string can be obtained by deleting some symbols in the string.
    • Examples
      • X = dynamic, Y = static, Z = aic
      • X = algorithms, Y = matchings, Z = aths
    • Solution
      • LCS(Xa,XbX_a, X_b) = LCS(X, Y) (if a=ba = b) or LCS(Xa,YX_a, Y) or LCS(X,YbX, Y_b) (if aba \neq b)
      • LengthLCS(Xa,XbX_a, X_b) = lengthLCS(X, Y) + 1 (if a=ba = b) or max{lengthLCS(Xa,YX_a, Y), lengthLCS(X,YbX, Y_b)} (if aba \neq b)
      • LCS(X,ϵ)=ϵLCS(X, \epsilon) = \epsilon, LCS(ϵ,Y)=ϵLCS(\epsilon, Y) = \epsilon, lengthLCS(ϵ,Y)=0lengthLCS(\epsilon, Y) = 0, lengthLCS(X,ϵ)=0lengthLCS(X, \epsilon) = 0.
    • Starting from the end/back of X and Y. Recursively apply the following function.
      • If the end symbols match, then remove the end symbols and call this algorithm again.
      • If the end symbols don’t match, then call this algorithm twice. Once on the full first string and the second string with the end symbol removed, and once on the first string with the end symbol removed and the full second string.
      • Subproblem is a prefix of X and a prefix of Y.
      • C[i,j]C[i,j] = value of the subproblem LCS(x1,...,xi,y1,...,yj)LCS(x_1, ..., x_i, y_1, ..., y_j).
    • The storage of the subproblem solutions is a 2D array where the rows are prefixes of Y and the columns are prefixes of X. Each cell holds the length of the LCS of x1,...,xix_1, ..., x_i and y1,...,yjy_1, ..., y_j. The output is the value at the top right of the 2D array.
      • Number of subproblems is Θ(nm)\Theta(nm) because subproblems is (n+1)(m+1)(n+1)(m+1). Since each subproblem takes constant time, the runtime is Θ(nm)\Theta(nm).
    • Printing the LCS
PrintLCS(C, n, m, X, Y)  # Call subroutine
PrintLCSRec(C, i, j, X, Y):  # Define subroutine
if i == 0 or j == 0:
    return
if C[i, j] == "Diagonal":
    PrintLCSRec(C, i - 1, j - 1, X, Y)
    print(X[i])
elif C[i, j] == "Horizontal":
    PrintLCSRec(C, i - 1, j, X, Y)
else:
    PrintLCSRec(C, i, j - 1, X, Y)

L17: (DP) Matrix problems

  • Matrix Chain Multiplication
    • Input
      • matrices A1,A2,..,AnA_1, A_2, .., A_n
      • integer n
      • dimensions p0,p1,...,pnp_0, p_1, ..., p_n. (Matrix AiA_i has dimensions (pi1,pip_{i-1}, p_i))
    • Output
      • the fastest way (order of multiplication) to compute the product B=A1A2...AnB = A_1 A_2 ... A_n.
    • Dimensions of B (p0,pn)(p_0, p_n), A1A_1 (p0,p1)(p_0, p_1), A2A_2 (p1,p2)(p_1, p_2), … AnA_n (pn1,pn)(p_{n-1}, p_n).
    • Cost of multiplying two matrices, one of (p,q)(p, q) and one of (q,r)(q, r), is pqrpqr.
    • Example
      • A1(4,6),A2(6,2),A3(2,2),B(4,2)A_1 (4, 6), A_2 (6, 2), A_3 (2, 2), B (4, 2)
      • Two multiplications: (A1A2)A3(A_1 A_2)A_3 or A1(A2A3)A_1(A_2 A_3).
      • The first one costs 64, the second one costs 72. So the first chain multiplication is cheaper.
    • The key insight is that there’s a last multiplication, we just don’t know where.
    • Last multiplication
      • Cost(A1n)=min{cost(A1k)+cost(A(k+1)n)+(p0pkpn)}Cost(A_{1-n}) = min\{cost(A_{1-k}) + cost(A_{(k+1)-n}) + (p_0p_kp_n)\} where 1kn11 \leq k \leq n - 1.
    • The cost equation is the smallest cost to compute the product (A1A2...An)(A_1A_2...A_n).
      • General cost: Cost(Aij)=min{cost(Aik)+cost(A(k+1)j)+(pi1pkpj)}Cost(A_{i-j}) = min\{cost(A_{i-k}) + cost(A_{(k + 1) - j}) + (p_{i-1}p_kp_j)\} where ikj1i \leq k \leq j - 1.
      • Base cases: Cost(Aii)=0Cost(A_{i-i}) = 0 where 1in1 \leq i \leq n.
    • Solution storage: C[i,j]=cost(Aij)C[i, j] = cost(A_{i-j}) which is a 2D array.
      • Rows are j, columns are i.
      • Output the cell at i = 1 and j = n so C[1,n]C[1, n].
      • Base cases are the diagonal so we get a diagonal of zeros.
      • We don’t use half of C (bottom-right triangle) because i must be less than j.
      • We fill out C diagonally.
      • Solving one cell in C requires the solutions down and right.
      • It takes Θ(n)\Theta(n) per cell for Θ(n2)\Theta(n^2) cells so the algorithm takes Θ(n3)\Theta(n^3).

L18: Algorithmic thinking

  • Problem 1 Asymptotics
    • f1=nlog4(n)f_1 = n log_4(n)
    • f2=4log2(n)f_2 = 4 log_2(n)
    • f3=n4f_3 = n^4
    • f4=n1/4f_4 = n^{1/4}
    • f5=2log4(n)=nlog4(2)=n0.5f_5 = 2^{log_4(n)} = n^{log_4(2)} = n^{0.5}
  • Running Times
    • S(n)=S(n)+n2nS(n) = S(\sqrt{n}) + \frac{n}{2} \approx n > T(n)=T(n2)+nnT(n) = T(\frac{n}{2}) + \sqrt{n} \approx \sqrt{n}
    • S(n)=4S(n2)+nlog(n)n2S(n) = 4S(\frac{n}{2}) + nlog(n) \approx n^2 > T(n)=8T(n4)+nlog(n)n2T(n) = 8T(\frac{n}{4}) + nlog(n) \approx n^2
    • S(n)=log(n!)nlog(n)S(n) = log(n!) \approx nlog(n), = T(n)=3T(n3)+nnlog(n)T(n) = 3T(\frac{n}{3}) + n \approx nlog(n)
    • S(n)=S(n2)+S(n2