CPSC 320 2009W2 Exam Reference Sheet
Do not remove: This reference sheet is the appendix for Midterm #1. Only the first 4 printed pages will be used; so be compact!
iff ![{\displaystyle \exists c\in \mathbf {R^{+}} ,\exists n_{0}\in \mathbf {Z^{+}} ,\forall n\in \mathbf {Z^{+}} ,n\geq n_{0}\rightarrow f(n)\leq cg(n)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/5ad067b315a89453e9bc4ab66ce6f0f19b7bab74)
iff
, ![{\displaystyle \exists c\in \mathbf {R^{+}} ,\exists n_{0}\in \mathbf {Z^{+}} ,\forall n\in \mathbf {Z^{+}} ,n\geq n_{0}\rightarrow 0\leq cg(n)\leq f(n)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/cc3246da37d99393c33b4035eb56af45536ad059)
iff
and
, ![{\displaystyle \exists c_{1},c_{2}\in \mathbf {R^{+}} ,\exists n_{0}\in \mathbf {Z^{+}} ,\forall n\in \mathbf {Z^{+}} ,n\geq n_{0}\rightarrow 0\leq c_{1}g(n)\leq f(n)\leq c_{2}g(n)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/0147a3cfed14784bfdb286fae6670456ee8195b9)
iff ![{\displaystyle \forall c\in \mathbf {R^{+}} ,\exists n_{0}\in \mathbf {Z^{+}} ,\forall n\in \mathbf {Z^{+}} ,n\geq n_{0}\rightarrow f(n)<cg(n)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/6aa6e5561c605d1feb163f0cea2080ec72b0c6e9)
iff
, ![{\displaystyle \forall c\in \mathbf {R^{+}} ,\exists n_{0}\in \mathbf {Z^{+}} ,\forall n\in \mathbf {Z^{+}} ,n\geq n_{0}\rightarrow 0\leq cg(n)<f(n)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/2bb004645d451d2ce6abbd3accc87ccfe4acdcef)
Also, if
, then ![{\displaystyle f(n)\in \omega (g(n))}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/3a52029c64a885b24fba54fc0513c6ec54c8be42)
- a non-zero constant, then
![{\displaystyle f(n)\in \Theta (g(n))}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/09e673203d32ca73205115ec3e2e80e918c01905)
, then ![{\displaystyle f(n)\in o(g(n))}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/540b11c5bbe6be7d47348bdac0ddeaa026eb5903)
(Plus bear in mind that (1) L'Hopital's rule may be handy, and (2) the limit is not always well-defined!)
L'Hopital's Rule:
If
or
, then
Analogy to Inequalities
if and only if ![{\displaystyle g(n)=\Omega (f(n))}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/5778f78725efc966a688ed3931bd099365611095)
if and only if ![{\displaystyle g(n)=\omega (f(n))}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/4a2fd58f2c4246aa0314a7fb3d45a28e7f055170)
It follows, where
and
:
![{\displaystyle f(n)=O(g(n))\approx a\leq b}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/2fa5749d6260c46a49ae9d219eba05b7e140d614)
![{\displaystyle f(n)=\Omega (g(n))\approx a\geq b}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/96e3eb3718454d801e6829ab6e2d263c62bcf5e3)
![{\displaystyle f(n)=\Theta (g(n))\approx a=b}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/fcf0989f4377136dad8027eccdf60897f22ce357)
![{\displaystyle f(n)=o(g(n))\approx a<b}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/dca77138ddc3b51d2b45933d6b8066bd2d735e89)
![{\displaystyle f(n)=\omega (g(n))\approx a>b}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/ccc69a65caab25b10fd091a18a5c148d7c795f07)
Caution: For all
exactly one must hold:
or
. Not all functions are asymptotically comparable.
Master Theorem
If
and a constant in the base case, where
can be either
or
,
and
then:
- If
for some
, then
- If
then,
- If
for some
and if
for some constant
and sufficiently large
, then
- Dominated by root cost - It is important in this case to check that f(n) is well behave. More specifically,
- For sufficient large n, a*f(n/b) <= c*f(n)
The following equations cannot be solved using the master theorem:
![{\displaystyle T(n)=2^{n}T\left({\frac {n}{2}}\right)+n^{n}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/f57f2a9f50b9144e6b007820d9367629e249cbbc)
a is not a constant
![{\displaystyle T(n)=2T\left({\frac {n}{2}}\right)+{\frac {n}{\log n}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/0087168fc93c6226a43c43e5a6efe4574c6992bc)
non-polynomial difference between f(n) and ![{\displaystyle n^{\log _{b}a}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/60c69530dba55a5f29400c6e9777fb1ae18e7024)
![{\displaystyle T(n)=0.5T\left({\frac {n}{2}}\right)+n}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/4a8c72d6c43b743bfb851bb2d8c0a5a3592cc66d)
a<1 cannot have less than one sub problem
![{\displaystyle T(n)=64T\left({\frac {n}{8}}\right)-n^{2}\log n}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/20cbfdcb2830f150cd5bdf2bed2b34fe5a0d2aec)
f(n) is not positive
![{\displaystyle T(n)=T\left({\frac {n}{2}}\right)+n(2-\cos n)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/03b8b924238e559f88461105a2524086762a7ce5)
case 3 but regularity violation.
Also, Case 3 always hold when f = n^k and If
Log Laws
For all real a > 0, b > 0, c > 0, and n,
![{\displaystyle a=b^{\log _{b}a}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/27c2377ae63681625e92113033babd08d49dba32)
![{\displaystyle \log _{c}ab=\log _{c}a+\log _{c}b}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/6dae7014449b2409012e672d404ccc5ff5e05e8c)
![{\displaystyle \log _{b}a^{n}=n\log _{b}a}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/2a2ce319595875eb1ea6e95b04d1612f336dd35b)
![{\displaystyle \log _{b}a={\frac {\log _{c}a}{\log _{c}b}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/3ee3e6a5a5f2ccb5bd60dcdf57805f323173e72b)
![{\displaystyle \log _{b}{\frac {1}{a}}=-\log _{b}a}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/8b4ab8ad20b1b0be442374f3d15185e2f6185ce2)
![{\displaystyle \log _{b}a={\frac {1}{\log _{a}b}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/afbd90f044a3e1c3866e76db5084d6440806b87e)
![{\displaystyle a^{\log _{b}c}=c^{\log _{b}a}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/16f5410f566d0437fa4e94f46fe96659a4676013)
![{\displaystyle \log 1=0}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/5cb25c36a737bdeb44ae03d88ba2254533cec559)
Summation
- Arithmetic Series:
![{\displaystyle \displaystyle {\sum _{k=1}^{n}(k)=1+2+\dots +n}={\frac {1}{2}}n(n+1)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/8693a8c250bfdf801267494975e08e7d558ede0e)
- Sum of Squares:
![{\displaystyle \displaystyle {\sum _{k=0}^{n}(k^{2})}={\frac {n(n+1)(2n+1)}{6}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/b431e690966752c5055711a5c0e817c48a441f8e)
- Sum of Cubes:
![{\displaystyle \displaystyle {\sum _{k=0}^{n}(k^{3})}={\frac {n^{2}(n+1)^{2}}{4}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/a89409215d696b377ca5698aac29e9871d6931b3)
- Geometric Series:
for real ![{\displaystyle x\neq 1}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/b9958361c7255c54e0e839727cf67a0f8ada2324)
- Infinite decreasing:
![{\displaystyle \displaystyle {\sum _{k=0}^{\infty }(x^{k})={\frac {1}{1-x}},for|x|<1}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/a76c3adb3e87b6b2e2a036b0c38feeba38b089d5)
- Telescoping:
![{\displaystyle \displaystyle {\sum _{k=1}^{n-1}(a_{k}-a_{k+1})=a_{0}-a_{n}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/73b148944e2aa7711cfe8c185a00230b77e363e4)
Exponents
![{\displaystyle a^{0}=1}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/448ca9a3f4ef03c4dfcf69258912d2c90b097842)
![{\displaystyle a^{1}=a}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/0f7545d7ed2d371323fca6aa910f4e9a41f86cd5)
![{\displaystyle a^{-1}={\frac {1}{a}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/782fa7c46e15fbb82c9002f8c9f72a3fceb8007f)
![{\displaystyle (a^{m})^{n}=a^{mn}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/9b430c76fcf7df71be0da8b4e721f4189e41c7ec)
![{\displaystyle a^{m}\times a^{n}=a^{m+n}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/87293bcd054eaedb02cebab51a389c6d3a767475)
Decision Tree-Related Notes
- for a list of
elements, there's
permutations
- a binary tree of height
has at most
leaves
- therefore, a binary tree with at least
leaves must have height at least ![{\displaystyle \lceil \lg n\rceil }](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/272552113a4aedb6df8c0da4d1c9e00452f8121b)
- to get the height of a tree: the longest path (say we divide by 3/2 at each level) finishes when
, so the height is ![{\displaystyle log_{\frac {3}{2}}n}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/d0b0e72fc293ff1403cb067d852232748fe17640)
, which we can establish by proving big-O and big-Ω bounds separately (pumping "up" or "down" the values of the terms in the factorial and the overall number of terms as needed)
Stirling's Approximation
![{\displaystyle \ln n!\sim n\ln n-n\ .}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/8bdb77aab9f40241c18d0e084e0f142a48b4fc85)
Derivatives
![{\displaystyle {\frac {d}{dx}}a^{f(x)}=a^{f(x)}*{\frac {d(f(x))}{dx}}ln(a)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/490f5de57dc880527d6d500e6d0c21fd7a424592)
![{\displaystyle {\frac {d}{dx}}\ln(x)={\frac {1}{x}},\qquad x>0}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/d8328ebbae475a173e1160205a277c70c0f5396d)
![{\displaystyle {\frac {d}{dx}}\log _{a}(x)={\frac {1}{x\ln(a)}}}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/3c9d408b97b303db79d6aec199219103bd22a4f5)
The Silicon Downs : Furlongs of Asymptotic Complexity
"NEWS FLASH: Mounties Find Silicon Downs Fixed!"
- Constant
![{\displaystyle \in O(1)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/87749657af2238b02fea59e1470ef0597a4c7719)
- Logarithmic
ie. ![{\displaystyle log_{k}n,logn^{2}\in O(logn)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/727ba6467d7281c6489442cc08761f32d00f2cf7)
- Poly-Log
![{\displaystyle \in O(log^{k}n)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/e1bb4ca894d5c61da0b9fd292dc53a3037e53246)
- Linear
![{\displaystyle \in O(n)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/ede74c83af73cd998e01754a68d1430d227b1fe0)
- Log-Linear
![{\displaystyle \in O(nlogn)}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/c66776373dc2a2c7a665158f1c65f1c768e64c40)
- Superlinear
where: c is a constant > 0
- Quadratic
![{\displaystyle \in O(n^{2})}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/0e42e439d5a016590c158c409241bb7c40e5d655)
- Cubic
![{\displaystyle \in O(n^{3})}](https://wiki.ubc.ca/api/rest_v1/media/math/render/svg/562fe1cb945f32430ee452365d2efe20f75bd484)
- Polynomial
where: k is a constant, "tractable"
- Exponential
where: c is a constant > 1, "intractable"
Stable Marriage Notes
Algorithm:
initialize all men in M and all women in W to unengage
while (an unengaged man with at least one woman on his preferance list remains)
do choose such a man m (element of) M
propose to the next woman w(element of)W on his preference list
if( w is unengaged)
then engage m to w
else if w prefers m to fiance m'
then break engagement of m' to w
engage m to w
cross w off m's preferance list
report set of engaged pairs as final matching.
Notes:
- All executions of the stable marriage sort produce the same matching, and all men end up with their "best possible partner".
- In the stable matching set each woman is paired with her worst valid partner.
- This algorithm terminates after at most
iterations of the while loop.
Skyline Problem & Algorithm
For input B[1..n] buildings as triples (left, height, right),
we get output of tuples (pos of height change, new height):
SKYLINE-ALG(B) {
If there is one building (x1,h,x2)
output (x1,h),(x2,0)
Else
divide into B1[1..floor(n/2)] and B2[floor(n/2)+1..n]
out1=SKYLINE-ALG(B1)
out2=SKYLINE-ALG(B2)
OUTPUT=MERGE(out1,out2)
}
The merge step is as follows:
MERGE(out1,out2) {
h1=h2=0, currx=0,curry=0
While out1 or out2 is not empty do {
If out1 and out2 start at the same x-coord
currx=first x-coord in out1
h1=first y-coord in out1
h2=first y-coord in out2
DELETE first entries in out1 and out2
Else If out1 has smallest first x-coord
currx=first x-coord in out1
h1=first y-coord in out1
DELETE first entry in out1
Else
currx=first x-coord in out2
h2=first y-coord in out2
DELETE first entry in out2
If max(h1,h2)!=curry
APPEND (currx,max(h1,h2)) to output
}
APPEND (currx,0) to output
}
Proving a Loop Invariant
- induction variable: Number of times through the loop
- base case: Prove the invariant true before the loop starts
- inductive hypothesis: Assume the invariant holds just before begininng some (unspecified) iteration of the loop.
- inductive step: prove the invariant holds at the end of that iteration (right before the next iteration)
- extra-bit: make sure the loop will eventually terminate.