Theoretical Computer Science Cheat Sheet

Theoretical Computer Science Cheat Sheet

Theoretical Computer Science Cheat Sheet
f (n) = O(g(n))
Denitions
i 9 positive c; n such that
0 f (n) cg(n) 8n n .
i 9 positive c; n such that
f (n) cg(n) 0 8n n .
i f (n) = O(g(n)) and
f (n) = (g(n)).
i limn!1 f (n)=g(n) = 0.
i 8 2 R , 9n such that
jan , aj < , 8n n .
least b 2 R such that b s,
8s 2 S .
greatest b 2 R such that b s, 8s 2 S .
lim inf fai j i n; i 2 N g.
n!1
n
X
0
0
f (n) = (g(n))
i
=1
In general:
0
f (n) = o(g(n))
nlim
!1 an = a
sup S
inf S
lim
inf a
n!1 n
k
n
k
1
n
18.
22.
25.
28.
+1
+1
+1
+1
i
i
n
X
i
1
n
n
X
ici = nc ,((cn,+1)1)c + c ; c 6= 1;
ici = (1 ,c c) ; c < 1:
i
i
=0
=0
+2
=1
+1
2
2
=0
Harmonic series:
n
X
Hn = 1i ;
n
X
i
i
=1
Hi = (n + 1)Hn , n;
1. nk = (n ,nk! )!k! ;
4. nk = nk nk ,, 11 ;
=1
=0
n
X
iHi = n(n2+ 1) Hn , n(n4, 1) :
i
n i
X
=1
i
=1
2.
n n
X
8.
m
n
k
=0
k
=0
Hn , m 1+ 1 :
+1
3. nk = n ,n k ;
5. nk = n ,k 1 + nk ,, 11 ;
X r + k r + n + 1
7.
;
k =
n
kn r + s
n r
X
s
9.
k n,k = n ;
k
n n
= m+1 ;
k , n , 1
10. k
k
n
12. 2 = 2n, , 1;
n
k =2 ;
n m n n , k 6. m k = k m , k ;
n k n + 1
X
2
n+1
m Hi = m + 1
= (,1)k
=0
;
n
1
1
=0
n n x + k X
n
x =
k
n ;
k
n X
n n n , k =0
n X
m n + 1
29. m =
(m + 1 , k)n (,1)k ;
k
k
n 31. m =
k
m
n k
n , 1 n , 1 34. k = (k + 1) k + (2n , 1 , k) k , 1 ;
X
n n x + n , 1 , k
36. x ,x n =
;
k
2n
k
=0
=0
n X
n n k 30. m! m =
k n,m ;
k
n =0
(,1)n,k,m k!;
=0
11. 1 = n = 1;
n , 1 n , 1
13. k = k k + k , 1 ;
n
n
n
n n
= (n , 1)!;
15.
= (n , 1)!Hn, ;
16. n = 1;
17. k k ;
n1 n , 1 n , 1 2 n n n
2n
n n
X
1
= (n , 1)
+ k , 1 ; 19. n , 1 = n , 1 = 2 ; 20.
= n!; 21. Cn = n + 1 n ;
kn n k
n n n k k n , 1 n , 1
=
= 1;
23. k = n , 1 , k ;
24. k = (k + 1) k + (n , k) k , 1 ;
00 n n , 1
n
n
n + 1
1
if
k
=
0,
n
n
n
26. 1 = 2 , n , 1;
27. 2 = 3 , (n + 1)2 + 2 ;
k = 0 otherwise
k
Cn
14.
=1
=1
=1
Combinations: Size k subsets of a size n set.
Stirling numbers (1st kind):
Arrangements of an n element set into k cycles.
Stirling numbers (2nd kind):
Partitions of an n element
set into k non-empty sets.
1st order Eulerian numbers:
Permutations : : : n on
f1; 2; : : :; ng with k ascents.
2nd order Eulerian numbers.
Catlan Numbers: Binary
trees with n + 1 vertices.
n
2
+1
n!1
k
2
3
1
0
n
i = n (n4+ 1) :
i
2
=1
0
n!1
,n
k
=1
n
X
n + 1) ;
i = n(n + 1)(2
6
n ,
X
i = m 1+ 1 (n + 1)m , 1 ,
(i + 1)m , im , (m + 1)im
i
i
m
nX
,
X
m + 1 B nm ,k :
im = m 1+ 1
k
k
i
k
Geometric series:
n
1
1
n
X
X
X
ci = c c ,,1 1 ; c 6= 1;
ci = 1 ,1 c ;
ci = 1 ,c c ; c < 1;
lim supfai j i n; i 2 N g.
lim sup an
i
n
X
m
0
f (n) = (g(n))
n
X
i = n(n2+ 1) ;
Series
32.
0
=0
33. n = 0 for n 6= 0;
n n (2n)n
X
35.
k = 2n ;
= 1;
k
n + 1 X n k X
n k
37.
=
=
(m + 1)n,k ;
=0
m+1
k
k
m
k
=0
m
Theoretical Computer Science Cheat Sheet
Identities Cont.
n + 1 X n k X
n k
n 1k
X
n
,
k
38. m + 1 =
k m = k m n = n! k k! m ;
k
n X n k + 1 =0
=0
=0
(,1)n,k ;
40. m =
k m+1
m + n +k1 X
m n + k
42.
= k k ;
m
Trees
Every tree with n
vertices has n , 1
edges.
Kraft
inequality: If the depths
of the leaves of
a binary tree are
d ; :n: : ; dn :
X ,di
2 1;
x X
n n x + k 39. x , n =
k
2n ;
k
X n + 1 k 41. mn =
(,1)m,k ;
k
+
1
m
m + n + 1k X
n + k
m
43.
k(n + k)
=
;
k
n X n +k 1 k n X n +m1 k k
44. m =
(,1)m,k ; 45. (n , m)! m =
(,1)m,k ; for n m,
k
+
1
m
k
+
1
m
n k X m , nm + n m + k n k X m , nm + n m + k =0
=0
i
47. n , m =
;
m
+
k
n
+
k
k
equality holds
n k` + m X k n , k n and
only if every in49. ` + m ` =
` m k : ternal node has 2
46. n , m =
m+k n+k
k ;
k
X k n , k n
48. ` +n m ` +` m =
`
m
k ;
k
Master method:
T (n) = aT (n=b) + f (n); a 1; b > 1
If 9 > 0 such that f (n) = O(n b a, )
then
T (n) = (n b a ):
If f (n) = (n b a ) then
T (n) = (n b a log n):
If 9 > 0 such that f (n) = (n b a ),
and 9c < 1 such that af (n=b) cf (n)
for large n, then
T (n) = (f (n)):
Substitution (example): Consider the
following recurrence
Ti = 2 i Ti ; T = 2:
Note that Ti is always a power of two.
Let ti = log Ti . Then we have
ti = 2i + 2ti ; t = 1:
Let ui = ti =2i . Dividing both sides of
the previous equation by 2i we get
ti = 2i + ti :
2i
2i
2i
log
log
log
log
2
log
2
+1
2
+
1
2
+1
1
+1
+1
+1
+1
Substituting we nd
ui = + ui ; u = 12;
which is simply ui = i=2. So we nd
that Ti has the closed form Ti = 2i i,1 .
Summing factors (example): Consider
the following recurrence
Ti = 3Tn= + n; T = n:
Rewrite so that all terms involving T
are on the left side
Ti , 3Tn= = n:
Now expand the recurrence, and choose
a factor which makes the left side \telescope"
+1
1
2
,
Recurrences
2
1 T (n) , 3T (n=2) = n
,
3 T (n=2) , 3T (n=4) = n=2
.. .. ..
. . .
,T (2) , 3T (1) = 2
n
,
3 2
,
3 2 n T (1) , 0 = 1
Summing the left side we get T (n). Summing the right side we get
log
1
log
X2 n n
log
i
2i 3 :
i
=0
Let c = andm = log n. Then we have
m
m
X
n ci = n c c , ,1 1
i
= 2n(c c 2 n , 1)
= 2n(c ck c n , 1)
= 2nk , 2n 2n :
, 2n;
where k = (log ), . Full history recurrences can often be changed to limited history ones (example): Consider the following recurrence
3
2
2
+1
=0
log
log
+1
1 58496
3
2 2
Ti = 1 +
1
i,
X
1
j
Tj ; T = 1:
0
=0
Note that
Ti = 1 +
+1
1
2
=1
k
1
2
1
Subtracting we nd
Ti , Ti = 1 +
+1
Xi
j
Xi
j
=0
= Ti :
And so Ti = 2Ti = 2i .
+1
+1
Generating functions:
1. Multiply both sides of the equation by xi .
2. Sum both sides over all i for
which the equation is valid.
3. Choose a generatingPfunction
i
G(x). Usually G(x) = 1
i x.
3. Rewrite the equation in terms of
the generating function G(x).
4. Solve for G(x).
5. The coecient of xi in G(x) is gi .
Example:
gi = 2gi + 1; g = 0:
Multiply
X andi sum:
X
X
gi x = 2gixi + xi :
=0
+1
0
+1
i
i
i
P
We choose G(x) = i xi . Rewrite
in terms of G(x):
X i
G(x) , g
0
0
0
0
x
0
= 2G(x) +
x:
i
0
Simplify:
G(x) = 2G(x) + 1 :
x
1,x
Solve for G(x):
x
G(x) = (1 , x)(1
, 2x) :
Expand this using partial fractions:
2
1
G(x) = x 1 , 2x , 1 , x
Tj :
=0
Tj , 1 ,
sons.
i,
X
1
j
=0
Tj
0
1
X
X
= x @2 2i xi , xi A
i
X ii
i
0
=
(2
i
i
So gi = 2 , 1.
0
+1
0
, 1)x :
+1
3:14159,
Theoretical Computer Science Cheat Sheet
p
e 2:71828,
0:57721,
=
1:61803,
2i
pi
1
2
2
2
4
3
3
8
5
4
16
7
5
32
11
6
64
13
7
128
17
8
256
19
9
512
23
10
1,024
29
11
2,048
31
12
4,096
37
13
8,192
41
14
16,384
43
15
32,768
47
16
65,536
53
17
131,072
59
18
262,144
61
19
524,288
67
20
1,048,576
71
21
2,097,152
73
22
4,194,304
79
23
8,388,608
83
24
16,777,216
89
25
33,554,432
97
26
67,108,864
101
27
134,217,728
103
28
268,435,456
107
29
536,870,912
109
30
1,073,741,824
113
31
2,147,483,648
127
32
4,294,967,296
131
Pascal's Triangle
1
11
121
1331
14641
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
i
1+
p
^ = , ,:61803
5
General
Bernoulli Numbers (Bi = 0, odd i 6= 1):
B = 1, B = , , B = , B = , ,
B = ,B =, ,B = .
Change of base, quadratic formula:
p
log
x
b , 4ac :
,
b
a
logb x = log b ;
2
a
a
Euler's number e:
e = 1+ + + + +
x n x
lim
1+ n =e :
n!1
0
1
1
6
30
5
10
30
1
4
6
1
8
42
1
2
2
1
66
2
1
1
1
1
2
6
24
120
,1 + n < e < ,1 + n :
n
n
,1 + n = e , e + 11e , O 1 :
1
+1
1
1
n
2n 24n
Harmonic numbers:
1, , , , , , ,
n
2
3
3
11
25
137
49
363
761
2
6
12
60
20
140
280
,
7129
2520
ln n < Hn < ln n + 1
;
Hn = ln n + + O n1 :
Factorial, Stirling's approximation:
1, 2, 6, 24, 120, 720, 5040, 40320, 362880,
p
n n
1 n! = 2n e
;:::
n
:::
E[X ] = k = 1k k pk qn,k = np:
Poisson distribution:
, k
Pr[X = k] = e k! ; E[X ] = :
Normal (Gaussian) distribution:
p(x) = p 1 e, x, 2 = 2 ; E[X ] = :
2
The \coupon collector": We are given a
random coupon each day, and there are n
dierent types of coupons. The distribution of coupons is uniform. The expected
number of days to pass before we to collect all n types is
(
)
nHn :
2
2
Probability
Continuous distributions:Z If
b
Pr[a < X < b] = p(x) dx;
a
then p is the probability density function of
X . If
Pr[X < a] = P (a);
then P is the distribution function of X . If
P and p both existZthen
a
P (a) =
p(x) dx:
,1
Expectation: If X is discrete
X
E[g(X )] = g(x) Pr[X = x]:
x
If X continuous
Z 1 then
Z1
E[g(X )] = g(x)p(x) dx = g(x) dP (x):
,1
,1
Variance, standard deviation:
VAR[X ] = E[X ] , E[X ] ;
p
= VAR[X ]:
Basics:
Pr[X _ Y ] = Pr[X ] + Pr[Y ] , Pr[X ^ Y ]
Pr[X ^ Y ] = Pr[X ] Pr[Y ];
i X and Y are independent.
X^Y]
Pr[X jY ] = Pr[Pr[
B]
E[X Y ] = E[X ] E[Y ];
i X and Y are independent.
E[X + Y ] = E[X ] + E[Y ];
E[cX ] = c E[X ]:
Bayes' theorem:
Pr[Ai jB ] = PnPr[B jAi ] Pr[Ai ] :
j Pr[Aj ] Pr[B jAj ]
Inclusion-exclusion:
n
h _n i X
Pr
Xi = Pr[Xi ] +
2
1+ n :
Ackermann's
8 jfunction and inverse:
i=1
<2
a(i; j ) = : a(i , 1; 2)
j=1
a(i , 1; a(i; j , 1)) i; j 2
(i) = minfj j a(j; j ) ig:
Binomial distribution:
Pr[X = k] = nk pk qn,k ;
q = 1 , p;
n
X
5
1
2
2
=1
i
=1
i
n
X
k
=1
(,1)k
+1
=1
X
ii <<ik
Pr
h ^k
j
Moment inequalities:
Pr jX j E[X ] 1 ;
=1
h
i
Pr X , E[X ] 1 :
Geometric distribution:
Pr[X = k] = pk, q;
q = 1 , p;
1
X
1
E[X ] = kpqk, = p :
2
1
1
k
=1
i
Xij :
Theoretical Computer Science Cheat Sheet
Trigonometry
Multiplication:
C = A B; ci;j =
(0,1)
A
b
C
(cos ; sin )
(-1,0)
c
(1,0)
a
B
2
2
det A =
2
+B :
2
=
AB; A +AB
B +C:
Permanents:
cos x = sec1 x ;
sin x + cos x = 1;
2
2
1 + cot x = csc x;
2
2
, sin x = cos , x ;
2
sin x = sin( , x);
cos x = , cos( , x);
, tan x = cot , x ;
cot x = , cot( , x);
csc x = cot x , cot x;
2
2
2
sin(x y) = sin x cos y cos x sin y;
cos(x y) = cos x cos y sin x sin y;
x tan y
tan(x y) = 1tan
tan x tan y ;
x cot y 1
cot(x y) = cot
cot x cot y ;
sin 2x = 2 tan x ;
1 + tan x
cos 2x = cos x , sin x;
cos 2x = 2 cos x , 1;
cos 2x = 1 , 2 sin x;
cos 2x = 1 , tan x ;
1 + tan x
2
tan
x
x , 1;
tan 2x =
;
cot 2x = cot2 cot
x
1 , tan x
sin(x + y) sin(x , y) = sin x , sin y;
sin 2x = 2 sin x cos x;
2
2
2
2
2
2
2
2
2
2
2
cos(x + y) cos(x , y) = cos x , sin y:
Euler's equation:
eix = cos x + i sin x; ei = ,1:
c 1994 by Steve Seiden
2
X Yn
i
a b c d e f = g b
g h i e
cos a = B=C;
sec a = C=B;
a = B:
cot a = cos
sin a A
Identities:
sin x = csc1 x ;
tan x = cot1 x ;
1 + tan x = sec x;
k
C
ai;k bk;j :
sign()ai; i :
=1
2
[email protected]
http://www.opt.math.tu-graz.ac.at/~seiden
b e
2
2
2
ai; i :
x ,x
cosh x = e + e ;
2
1
csch x = sinh x ;
1 :
coth x = tanh
x
2
2
0
6
4
3
2
2
2
sin cos tan 0
p1
p0
p
p
p
3
2
0
1
2
2
2
3
1
3
2
2
2
1
2
3
1
p
3
1
Heron's formula:
More identities:
r
x
sin = 1 , 2cos x ;
2
r
1 + cos x ;
r 1 , 2cos x
tan x = 1 + cos x ;
x
= 1 ,sincos
x ;
x ;
= 1 +sincos
r 1 + cosx x
cot x = 1 , cos x ;
x
= 1 +sincos
x ;
x ;
= 1 ,sincos
x
ix
,
ix
sin x = e ,2ie ;
ix ,ix
cos x = e +2e ;
ix , e,ix
tan x = ,i eeix +
e,ix ;
ix 1
= ,i ee ix ,
+ 1;
sin x = sinhi ix ;
cos x = cosh ix;
tan x = tanh ix :
2
2
2
2
cos x =
2
2
2
2
Identities:
cosh x , sinh x = 1;
tanh x + sech x = 1;
coth x , csch x = 1;
sinh(,x) = , sinh x;
cosh(,x) = cosh x;
tanh(,x) = , tanh x;
sinh(x + y) = sinh x cosh y + cosh x sinh y;
cosh(x + y) = cosh x cosh y + sinh x sinh y;
sinh 2x = 2 sinh x cosh x;
cosh 2x = cosh x + sinh x;
cosh x + sinh x = ex;
cosh x , sinh x = e,x;
(cosh x + sinh x)n = cosh nx + sinh nx; n 2 Z;
2 sinh x = cosh x , 1; 2 cosh x = cosh x + 1:
2
1
1
Hyperbolic Functions
x e,x
tanh x = eex ,
+ e,x ;
1 ;
sech x = cosh
x
A = hc;
= ab sin C;
A sin B :
= c sin
2 sin C
A = ps sa sb sc ;
s = (a + b + c);
sa = s , a;
sb = s , b;
sc = s , c:
=1
Denitions:
x ,x
sinh x = e ,2e ;
2
2
( )
i
2
1
aei + bfg + cdh
, ceg , fha , ibd:
X Yn
Law of cosines:
c = a +b ,2ab cos C:
Area:
2
( )
c , h a c + i a
f d f d
perm A =
b h a
A
c
B
=1
2 2 and 3 3 determinant:
a b c d = ad , bc;
2
Area, radius of inscribed circle:
1
n
X
More Trig.
Determinants: det A = 0 i A is non-singular.
det A B = det A det B;
(0,-1)
Pythagorean theorem:
C =A
Denitions:
sin a = A=C;
csc a = C=A;
sin a = A ;
tan a = cos
a B
Matrices
: : : in mathematics
you don't understand things, you
just get used to
them.
{ J. von Neumann
2
2
2
2
i
Theoretical Computer Science Cheat Sheet
Number Theory
The Chinese remainder theorem: There exists a number C such that:
C r mod m
1
1
.. .. ..
. . .
C rn mod mn
if mi and mj are relatively prime for i 6= j .
Euler's function: (x) is the number of
positive integersQ less than x relatively
prime to x. If ni pei i is the prime factorization of x then
Yn
(x) = pei i , (pi , 1):
=1
1
i
=1
Euler's theorem: If a and b are relatively
prime then
1 a b mod b:
Fermat's theorem:
1 ap, mod p:
The Euclidean algorithm: if a > b are integers then
gcd(a; b) = gcd(a mod b; b):
Q
n
If i pei i is the prime factorization of x
then
n ei
X Y
S (x) = d = pip ,,1 1 :
( )
1
=1
+1
djx
i
=1
i
Perfect Numbers: x is an even perfect number i x = 2n, (2n , 1) and 2n , 1 is prime.
Wilson's theorem: n is a prime i
(n , 1)! ,1 mod n:
Mobius 8
inversion:
if i = 1.
>
< 10
square-free.
(i) = > (,1)r ifif ii isis not
the
product
of
:
r distinct primes.
If
X
G(a) = F (d);
1
then
F (a) =
dja
Prime numbers:
pn = n ln n + n ln ln n , n + n lnlnlnnn
+ O lnnn ;
(n) = lnnn + (lnnn) + (ln2!nn)
2
+ O (lnnn) :
4
0
1
1
1
3
0
2
1
2
0
1
1
0
1
0
1
1
0
1
0
2
0
0
1
1
0
0
2
1
2
1
0
1
0
2
0
2
0
1
1
2
1
1
(d)G da :
dja
X
Graph Theory
Notation:
Denitions:
E (G) Edge set
Loop
An edge connecting a verV (G) Vertex set
tex to itself.
c(G) Number of components
Directed
Each edge has a direction.
G[S ] Induced subgraph
Simple
Graph with no loops or
deg(v) Degree of v
multi-edges.
(G) Maximum degree
Walk
A sequence v e v : : : e`v` .
(G) Minimum degree
Trail
A walk with distinct edges.
(G) Chromatic number
Path
A trail with distinct
E (G) Edge chromatic number
vertices.
Gc
Complement graph
Connected A graph where there exists
K
Complete graph
n
a path between any two
K
n1 ;n2 Complete bipartite graph
vertices.
r(
k;
`) Ramsey number
Component A maximal connected
subgraph.
Geometry
Tree
A connected acyclic graph.
Projective coordinates: triples
Free tree
A tree with no root.
(x; y; z ), not all x, y and z zero.
DAG
Directed acyclic graph.
(x; y; z ) = (cx; cy; cz ) 8c 6= 0:
Eulerian
Graph with a trail visiting
Cartesian
Projective
each edge exactly once.
Hamiltonian Graph with a path visiting
(x; y)
(x; y; 1)
each vertex exactly once.
y = mx + b (m; ,1; b)
Cut
A set of edges whose rex=c
(1; 0; ,c)
moval increases the numDistance formula, Lp and L1
ber of components.
metric:
p
Cut-set
A minimal cut.
(x , x ) + (x , x ) ;
Cut edge
A size 1 cut.
jx , x jp + jx , x jp =p;
k-Connected A graph connected with
jx , x jp + jx , x jp =p:
the removal of any k , 1
lim
p!1
vertices.
Area
of triangle (x ; y ), (x ; y )
k-Tough
8S V; S 6= ; we have
and
(
x
; y ):
k c(G , S ) jS j.
k-Regular A graph where all vertices
x
,
x
y
,
y
abs x , x y , y :
have degree k.
k-Factor
A k-regular spanning
Angle formed by three points:
subgraph.
B
Matching A set of edges, no two of
which are adjacent.
cos = (x ; y `) `(x ; y ) :
Clique
A set of vertices, all of
which are adjacent.
Line through two points (x ; y )
Ind. set
A set of vertices, none of
and (x ;y ):
which are adjacent.
x y 1 Vertex cover A set of vertices which
x y 1 = 0:
cover all edges.
x y 1
Planar graph A graph which can be emArea of circle, volume of sphere:
beded in the plane.
A = r ; V = r :
Plane graph An embedding of a planar
graph.
2
2
1
0
0
1
1
2
4
3
3
X
v2V
deg(v) = 2m:
If G is planar then n , m + f = 2, so
f 2n , 4; m 3n , 6:
Any planar graph has a vertex with degree 5.
If I have seen farther than others,
it is because I have stood on the
shoulders of giants.
{ Issac Newton
Theoretical Computer Science Cheat Sheet
Wallis' identity:
= 2 12 32 34 45 65 67 Brouncker's continued fraction expansion:
1
=1+
2
2+
52
2
4
3
2+ 2+72
2+
Gregrory's series:
= 1, + , + ,
Newton's series:
1
13
=1+
2 2 32 + 2 45 2 +
Sharp's series:
= p1 1 , 1 + 1 , 1 + 3 3 3 5 3 7
3
Euler's series:
4
1
1
1
1
3
5
7
9
6
3
6
5
1
2
3
2 = 2 + 2 + 2 + 2 + 2 + 2 = 2 + 2 + 2 + 2 + 2 + 2 = 2 , 2 + 2 , 2 + 2 , 1
6
1
1
8
1
12
1
1
1
2
1
3
1
2
1
3
1
5
1
3
1
1
4
5
1
1
7
9
1
1
4
5
Partial Fractions
Let N (x) and D(x) be polynomial functions of x.
We can break down
N (x)=D(x) using partial fraction expansion. First, if the degree of N is greater
than or equal to the degree of D, divide
N by D, obtaining
N (x) = Q(x) + N 0 (x) ;
D(x)
D(x)
where the degree of N 0 is less than that of
D. Second, factor D(x). Use the following rules: For a non-repeated factor:
N (x) = A + N 0 (x) ;
(x , a)D(x) x , a D(x)
where
(x) A= N
:
D(x)
x a
Derivatives:
1. d(cu) = c du ;
d(u + v) = du + dv ;
d(uv) = u dv + v du ;
2.
3.
dx
dx
dx
dx, dx , dx
dx dx
du , u dv
n)
cu )
v
d
(
u
du
d
(
u=v
)
d
(
e
4. dx = nun, dx ; 5. dx = dx v dx ; 6. dx = cecu du
dx ;
u
u) 1 du
7. d(dxc ) = (ln c)cu du
8. d(ln
dx ;
dx = u dx ;
1
2
du
u)
9. d(sin
dx = cos u dx ;
u)
du
11. d(tan
dx = sec u dx ;
1
where
=0
dk N (x)
Ak = k1! dx
k D(x)
x a
:
=
The reasonable man adapts himself to the
world; the unreasonable persists in trying
to adapt the world to himself. Therefore
all progress depends on the unreasonable.
{ George Bernard Shaw
u)
du
10. d(cos
dx = , sin u dx ;
u)
du
12. d(cot
dx = csc u dx ;
2
2
u) = tan u sec u du ;
13. d(sec
dx
dx
d
(arcsin
u
)
1
15. dx = p1 , u du
dx ;
u) = , cot u csc u du ;
14. d(csc
dx
dx
d
(arccos
u
)
,
1
du
16. dx = p1 , u dx ;
u) = ,1 du ;
18. d(arccot
dx
1 , u dx
u)
,1 du
20. d(arccsc
dx = up1 , u dx ;
2
2
u) = 1 du ;
17. d(arctan
dx
1 , u dx
u)
1 du
19. d(arcsec
dx = up1 , u dx ;
2
2
2
2
u)
du
21. d(sinh
dx = cosh u dx ;
u) = sech u du ;
23. d(tanh
dx
dx
u)
du
22. d(cosh
dx = sinh u dx ;
u) = , csch u du ;
24. d(coth
dx
dx
2
2
u)
du
25. d(sech
dx = , sech u tanh u dx ;
u) = p 1 du ;
27. d(arcsinh
dx
1 + u dx
u)
du
26. d(csch
dx = , csch u coth u dx ;
u) = p 1 du ;
28. d(arccosh
dx
u , 1 dx
2
2
u) = 1 du ;
29. d(arctanh
dx
1 , u dx
u) = p,1 du ;
31. d(arcsech
dx
u 1 , u dx
u) = 1 du ;
30. d(arccoth
dx
u , 1 dx
u) = p,1 du :
32. d(arccsch
dx
juj 1 + u dx
2
2
2
Integrals:
1.
3.
=
For a repeated factor:
mX
,
N (x)
Ak + N 0 (x) ;
=
(x , a)m D(x) k (x , a)m,k D(x)
Calculus
6.
8.
Z
Z
xn dx = n +1 1 xn ; n 6= ,1;
12.
14.
4.
+1
Z dx
Z 1+x
2
Z
Z
Z
Z
Z
1 dx = ln x;
5.
Z
2. (u + v) dx = u dx + v dx;
cu dx = c u dx;
Z
10.
2
Z
x
7.
= arctan x;
tan x dx = , ln j cos xj;
13.
sec x dx = ln j sec x + tan xj;
p
arcsin xa dx = arcsin xa + a , x ; a > 0;
2
2
Z
ex dx = ex;
Z dv
Z du
u dx dx = uv , v dx
dx;
Z
9.
sin x dx = , cos x;
Z
11.
Z
cos x dx = sin x;
cot x dx = ln j cos xj;
csc x dx = ln j csc x + cot xj;
Theoretical Computer Science Cheat Sheet
15.
17.
19.
21.
23.
25.
26.
29.
33.
36.
Z
Z
Z
Z
Z
Z
Z
Z
Z
Z
p
Calculus Cont.
16.
arccos xa dx = arccos xa , a , x ; a > 0;
sin (ax)dx = a
2
1
2
2
2
,ax , sin(ax) cos(ax);
39.
40.
Z
Z
arctan xa dx = x arctan xa , a ln(a + x ); a > 0;
2
Z
18.
2
2
,
cos (ax)dx = a ax + sin(ax) cos(ax) ;
2
1
Z
2
20.
sec x dx = tan x;
2
csc x dx = , cot x;
2
Z
Z
n,
n,
1 Z sinn, x dx;
n x dx = cos x sin x + n , 1 cosn, x dx;
22.
cos
sinn x dx = , sin nx cos x + n ,
n
n
n
Z
Z
Z
n
,
n
,
x
n,
tann x dx = tan
24. cotn x dx = , cotn , 1 x , cotn, x dx; n 6= 1;
n , 1 , tan x dx; n 6= 1;
n, x n , 2 Z
n,
secn x dx = tan xnsec
, 1 + n , 1 sec x dx; n 6= 1;
Z
Z
n, x n , 2 Z
cot
x
csc
n
,
n
+ n , 1 csc x dx; n 6= 1; 27. sinh x dx = cosh x; 28. cosh x dx = sinh x;
csc x dx = , n , 1
1
1
2
2
1
1
2
2
1
2
1
2
tanh x dx = ln j cosh xj; 30.
Z
coth x dx = ln j sinh xj; 31.
2
1
1
4
2
p
Z
34.
sinh x dx = sinh(2x) , x;
Z
1
2
37.
2
p
2
2
2
2
2
2
41.
1
2
p
42. (a , x ) = dx = x (5a , 2x ) a , x +
2
2 3 2
2
2
2
2
Z
sech x dx = tanh x;
2
arctanh xa dx = x arctanh xa + a ln ja , x j;
2
2
2
if arccosh xa < 0 and a > 0,
2
2
Z
2
2
if arccosh xa > 0 and a > 0,
= ln x + a + x ; a > 0;
a +x
dx = arctan x ; a > 0;
a
a +x a
2
1
4
csch x dx = ln tanh x ;
35.
cosh x dx = sinh(2x) + x;
2
Z
sech x dx = arctan sinh x; 32.
arcsinh xa dx = x arcsinh xa , x + a ; a > 0;
p
8
<
x arccosh xa , x + a ;
38. arccosh xa dx = :
p
x arccosh xa + x + a ;
Z dx
p
Z
Z
a4 arcsin x ;
a
3
Zp
p
a , x dx = x a , x + a2 arcsin xa ; a > 0;
2
2
2
2
2
2
a > 0;
a + x Z dx
Z
1
dx
x
p
44. a , x = 2a ln a , x ;
43.
= arcsin a ; a > 0;
45. (a ,dxx ) = = a pax , x ;
a ,x
Z dx
Zp
p
p
p
2 x
a
a x dx = a x ln x + a x ;
47. px , a = ln x + x , a ; a > 0;
46.
x Z dx
Z p
1
a)(a + bx) = ;
48. ax + bx = a ln a + bx ;
49. x a + bx dx = 2(3bx , 215
pa + bx , pab Z 1
Z pa + bx
Z x
p
1
dx = 2 a + bx + a p
50.
dx;
51. pa + bx dx = p2 ln pa + bx + pa ; a > 0;
x
x
a
+
bx
Z p
Z pa , x
a + pa , x p
a
,
x
,
a
ln
dx
=
;
53.
x a , x dx = , (a , x ) = ;
52.
x
x
p
Z p
Z dx
p
4
a
+
a
,
x
;
x
a
x
54. x a , x dx = (2x , a ) a , x + arcsin a ; a > 0;
55. pa , x = , a ln x
Z x dx
Z x dx
p
p
56. pa , x = , a , x ;
57. pa , x = , x a , x + a2 arcsin a;x a > 0;
p
Z pa + x
Z px , a
p
p
a
+
a
+
x
dx = a + x , a ln dx = x , a , a arccos a ; a > 0;
58.
59.
;
Z
8
2
2
2
2
8
2
2
2
2
2
2
2
2 3 2
2
2
2
2
2
2
2
2
2
3 2
2
2
2
2
2
2
2
2
2
1
2
2
2 3 2
3
2
2
2
2
2
2
2
1
2
8
8
2
2
2
2
2
60.
2
2
2
2
Z p
2
2
x
2
2
x x a dx = (x a
2
2
1
3
2
)=
2 3 2
;
2
x
2
2
2
2
2
x
61.
2
2
Z
2
2
jxj
2
dx
p
= a ln px
x x +a
a+ a +x
1
2
2
2
2
;
62.
64.
66.
Z
Z
Theoretical Computer Science Cheat Sheet
Calculus Cont.
Finite Calculus
p
Z
Dierence, shift operators:
p dx = a arccos jxaj ; a > 0;
p dx
63.
= xa x a ;
f (x) = f (x + 1) , f (x);
x x ,a
p x x a
Z
=
p
x a dx = (x + a ) ;
E f (x) = f (x + 1):
p x dx = x a ;
65.
Fundamental Theorem:
3a x
x a
8
X
p x >
1
b
,
4
ac
2
ax
+
b
,
f
(
x
)
=
F
(
x
)
,
f (x)x = F (x) + C:
>
< pb , 4ac ln 2ax + b + pb , 4ac ; if b > 4ac,
dx
b
b,
X
X
ax + bx + c = >
f
(
x
)
x
=
f (i):
2
2
ax
+
b
>
:p
arctan p
;
if b < 4ac,
a
i
a
4ac , b
4ac , b
Dierences:
8 1 p
p
(cu) = cu;
(u + v) = u + v;
>
< pa ln 2ax + b + 2 a ax + bx + c ; if a > 0,
dx
(uv) = uv + E vu;
p
=
1
,
2
ax
,
b
ax + bx + c >
: p,a arcsin pb , 4ac ;
if a < 0,
(xn ) = nxn, ;
(2x) = 2x ;
(Hx ) = x, ;
Z
p
p
,
, 2
ax
+
b
4
ax
,
b
dx
p
ax + bx + c dx =
ax + bx + c +
;
(cx ) = (c , 1)cx;
x = x :
2
1
2
2
2
2
2
2
Z
2
2
2
2
2
2
2 3 2
2
4
2
2
3
2
2
2
2
1
2
2
2
67.
Z
=
2
2
2
1
68.
69.
70.
71.
72.
73.
74.
75.
76.
Z
2
1
2
2
Z
2
4a
p
2
Z
Z
Z
Z
Z
2
2
1
2
2
3
2
2
5
1
2
3
4
5
if c < 0,
c,
2 3 2
Z
xn cos(ax) dx = a xn sin(ax) , na xn, sin(ax) dx;
1
Z
xn ln(ax) dx = xn
+1
xn (ln ax)m dx =
x
2
+1
n+1
(ln ax)m ,
x +x
x + 3x + x
x + 6x + 7x + x
x + 15x + 25x + 10x + x
1
2
3
4
1
3
5
2
4
1
3
2
1
1
2
3
4
5
1
2
3
4
1
2
3
1
2
m
Rising Factorial Powers:
xn = x(x + 1) (x + m , 1); n > 0;
x = 1;
xn = (x , 1) 1 (x , jnj) ; n < 0;
1
Z
;
0
n
m,
n + 1 x (ln ax) dx:
=
=
=
=
=
1
2
1
n + 1 , (n + 1)
xn
+
1
ln(ax)
x
x
x
x
x
1
2
3
4
5
+1
xn m = xm (x , m)n :
1
n ax
xn eax dx = x ae , na xn, eax dx;
m
0
1
1
m
1
Falling Factorial Powers:
xn = x(x , 1) (x , m + 1); n > 0;
x = 1;
xn = (x + 1) 1 (x + jnj) ; n < 0;
xn sin(ax) dx = , a xn cos(ax) + na xn, cos(ax) dx;
=
x
=
x +x
=
x + 3x + 2x
=
x + 6x + 11x + 6x
= x + 10x + 35x + 50x + 24x
4
+1
15
x
x
x
x
x
3
1
2
3
1
P cu x = c P u x;
P(u + v) x = P u x + P v x;
P uv x = uv , P E vu x;
P xn x = xn+1 ;
P x, x = H ;
x
m
P , x x = , x :
P cx x = cx ;
if c > 0,
2
Z
m,
m
Sums:
2
8 ,1 2pcpax + bx + c + bx + 2c >
;
>
p
ln <
c
x
p dx
=>
x ax + bx + c > 1
: p,c arcsin jxjpbxb+,2c4ac ;
p
x x + a dx = ( x , a )(x + a ) = ;
Z
=
=
=
=
=
1
2
2
2
Z
ax + bx + c
Z
= ax +a bx + c , 2ba p dx
;
ax + bx + c
ax + bx + c
p x dx
x
x
x
x
x
2
8a
1
x
xn m = xm (x + m)n :
+
Conversion:
xn = (,1)n (,x)n = (x , m + 1)n
= 1=(x + 1),n ;
xn = (,1)n (,x)n = (x + m , 1)n
= 1=(x , 1),n ;
1
x ,x
x , 3x + x
x , 6x + 7x , x
x , 15x + 25x , 10x + x
2
3
1
2
4
1
3
5
2
4
1
3
2
1
=
x
=
x ,x
=
x , 3x + 2x
=
x , 6x + 11x , 6x
= x , 10x + 35x , 50x + 24x
1
2
3
4
5
1
2
3
4
1
2
3
1
2
1
n n
n n
X
X
n
k
x =
x =
(,1)n,k xk ;
k
k
k
k
n n
X
xn =
(,1)n,k xk ;
k
k
n n
X
xn =
xk :
k
k
=1
=1
=1
=1
Theoretical Computer Science Cheat Sheet
Series
Taylor's series:
1
i
X
f (x) = f (a) + (x , a)f 0 (a) + (x ,2 a) f 00 (a) + = (x ,i! a) f i (a):
i
Expansions:
1
X
1
=
1
+
x
+
x
+
x
+
x
+
=
xi ;
1,x
Ordinary power series:
2
A(x) =
( )
=0
2
1
3
1 , cx
1
1 , xn
= 1 + cx + c x + c x + (1 , x)
n 1 d
k
x dxn 1 , x
= x + 2x + 3x + 4x + ex
= 1+x + x + x +
2
2
3
3
= 1 + xn + x n + x n + 2
3
=
=
1
X
=0
A(x) =
=0
i
1
X
ci xi ;
2
2
3
4
=
1
X
= x + 2nx + 3nx + 4n x + =
2
3
4
i
A(x) =
xni ;
1
2
2
3
6
= x , x + x , x ,
ln(1 + x)
1
1
2
2
1
3
3
4
4
=
=0
k
i xi ;
i
=0
= x + x + x + x +
sin x
= x , x + x , x +
1
1
2
2
1
3
3
4
4
i
= (,1)i xi ;
i
1 xi
X
=
;
i i
1
i
X
= (,1)i (2xi + 1)! ;
i
1
i
X
= (,1)i (2xi)! ;
i
1
i
X
= (,1)i (2xi + 1) ;
i 1 n
X
=
xi ;
i
i 1 i + n
X
=
xi ;
i
i
1
i
X
= Bii!x ;
i
1
X
= i +1 1 2ii xi ;
i 1 2i
X
=
xi ;
i
i 1 2i + n
X
=
xi ;
i
i
+1
1
1
3
1
5
5!
7
7!
2 +1
=0
= 1, x + x , x +
cos x
1
1
2
2!
1
4
4!
6
6!
2
A(x) + B (x) =
xk A(x) =
= x , x + x , x +
1
1
1
3
3
1
5
5
7
7
= 1 + nx + n n, x + (
, = 1 + (n + 1)x + n x + +2
(1 , x)n
2
2
+1
x
=1, x+ x ,
1 (1 , p1 , 4x)
2x
p1 ,1 4x
1 , p1 , 4x n
p 1
2x
1 , 4x
1 ln 1
1,x 1,x
1 ln 1
2
1,x
1
2
12
1
2
xk
720
x +
4
= 1 + x + 2x + 5x + 3
=0
= 1 + x + 2x + 6 x + 2
3
= 1 + (2 + n)x +
, nx + 4+
2
2
=0
1
X
=0
= x + x + x + x + =
3
11
2
2
25
3
6
4
12
i
Hi xi ;
1 H xi
X
i,
=1
= x + x + x +
1
3
2
2
11
3
4
4
24
=
i
1
X
=2
= x + x + 2x + 3x + 2
2
3
4
=
i
1
X
i
1
Fi xi ;
=0
2
= Fn x + F n x + F n x + 2
2
3
3
=
i
=0
Fni xi :
;
=0
1
X
i
(ai + bi )xi ;
1
X
=0
ai,k xi ;
=0
A(cx) =
A0 (x) =
=0
=0
2
2
x
1,x,x
Fn x
1 , (Fn, + Fn )x , (,1)n x
1
1
=0
2 +1
=0
ex , 1
+1
2
2
1
1
1)
k
xn, ,k yk :
1
=0
(1 + x)n
1
i
P
1
k
,
i
A(x) , i ai x = X
ai,k xi ;
=0
tan, x
nX
,
For ordinary power series:
=1
3!
=0
xn , yn = (x , y)
i! ;
=1
ln 1 ,1 x
ix :
Dierence of like powers:
1 xi
X
1
X
i
Binomial theorem: n n
X
n,k k
(x + y)n =
k x y:
ixi ;
1
X
n
i
1 a
X
i
=1
=0
1
i
=0
=0
x
1 xi
X
ai i! :
Dirichlet power series:
=0
i
i
ai xi :
Exponential power series:
4
i
1
X
Z
xA0 (x) =
A(x) dx =
1
X
i
i
ci ai xi ;
=0
1
X
i
=0
(i + 1)ai xi ;
+1
1
X
i
=0
iai xi ;
1 a
X
i,
=1
i
i x;
1
i
1
A(x) + A(,x) = X
a ix i;
2
i
=1
2
1
A(x) , A(,x) = X
a
2
=0
i
i x :
2
i
P
Summation: If bi = ij ai then
B (x) = 1 ,1 x A(x):
Convolution: 0
1
2 +1
2 +1
=0
=0
A(x)B (x) =
1 X
i
X
@
i
=0
j
aj bi,j A xi :
=0
God made the natural numbers;
all the rest is the work of man.
{ Leopold Kronecker
Theoretical Computer Science Cheat Sheet
Expansions:
1
1
(1 , x)n ln 1 , x
+1
xn
n
ln 1 ,1 x
Series
=
1
X
1 ,n
(Hn i , Hn ) n +i i xi ;
i 1
=
x
+
X n i
=
x;
i1 i X i n!xi
=0
(ex , 1)n =
i! ;
X i i
= (,4)(2Bi)!i x ;
i
i
n
i1
=0
n i! ;
1
X
1 i
X
xi ;
n
i 1 i n!xi
X
=0
=0
=
Escher's Knot
x cot x
2
2
1
i i
i,
X
tan x
= (,1)i, 2 (2 ,(21)i)!B i x ;
(x)
= i1x ;
i
i
1 (i)
1 (i)
X
X
1
(
x
,
1)
=
=
(x)
ix ;
(x)
ix ;
i
i
Y
(x)
= 1 ,1p,x ;
Stieltjes Integration
p
If G is continuous in the interval [a; b] and F is nondecreasing then
1 d(i)
X
P
Zb
(x)
=
where
d
(
n
)
=
1
;
d
j
n
i
G(x) dF (x)
i x
a
1
X
P
exists. If a b c then
(x) (x , 1)
= Sx(ii) where S (n) = djn d;
Zc
Zb
Zc
i
G
(x) dF (x) = G(x) dF (x) + G(x) dF (x):
n,
a
a
b
nj n; n 2 N ;
(2n)
= 2 (2njB
If
the
integrals
involved
exist
)!
Z b,
dF (x) = Z b G(x) dF (x) + Z b H (x) dF (x);
1
i , 2)B i x i
X
(4
x
G
(
x
)
+
H
(
x
)
= (,1)i,
;
sin x
(2i)!
Zab
Zab
Za b
i
,
1 , p1 , 4x n X
1 n(2i + n , 1)!
G(x) d F (x) + H (x) = G(x) dF (x) + G(x) dH (x);
i;
a
=
x
Z
Zb a,
Z ab
2x
i!(n + i)!
b
i
c G(x) dF (x) = G(x) d c F (x) = c G(x) dF (x);
1 2i= sin i
X
a
a
i;
ex sin x
=
x
Zb
Z ba
i
!
i
G(x) dF (x) = G(b)F (b) , G(a)F (a) , F (x) dG(x):
s p
a
a
1
X
1, 1,x
(4
i
)!
i
If
the
integrals
involved
exist,
and
F
possesses
a
derivative
F 0 at every
p
x;
=
i
x
point in [a; b] then
i 16 2(2i)!(2i + 1)!
arcsin x Zb
Zb
1
i
X 4 i!
i
G(x) dF (x) = G(x)F 0 (x) dx:
= (i + 1)(2i + 1)! x :
x
a
a
i
Crammer's Rule
Fibonacci Numbers
If we have equations:
1; 1; 2; 3; 5; 8; 13; 21; 34; 55; 89; : : :
a ; x + a ; x + + a ;n xn = b
Denitions:
a ; x + a ; x + + a ;n xn = b
Fi = Fi, +Fi, ; F = F = 1;
..
..
..
.
.
.
F,i = (,
1)i, Fi;
an; x + an; x + + an;n xn = bn
Fi = p i , ^i ;
Let A = (ai;j ) and B be the column matrix (bi ). Then
Cassini's identity: for i > 0:
there is a unique solution i det A 6= 0. Let Ai be A
Fi Fi, , Fi = (,1)i :
with column i replaced by B . Then
Ai :
Additive rule:
The Fibonacci number system:
xi = det
det A
Fn k = Fk Fn + Fk, Fn ;
Every integer n has a unique
representation
F n = Fn Fn + Fn, Fn :
Improvement makes strait roads, but the crooked
n = Fk1 + Fk2 + + Fkm ;
Calculation
F F by matrices:
n
roads without Improvement, are roads of Genius.
where ki ki + 2 for all i,
n,
n, = 0 1 :
{ William Blake (The Marriage of Heaven and Hell)
1 i < m and km 2.
Fn, Fn
1 1
=0
2
=0
2
2
1
2
1
=1
=1
=1
=1
2
=1
=1
2
1
2
2
2
1
2
=0
=0
2
4
=1
=0
2
2
2
=0
1 1
1
1 2
2
1
1
2 1
1
2 2
2
2
2
1
1
2
2
0
47
18
76
29
93
85
34
61
52
86
11
57
28
70
39
94
45
2
63
95
80
22
67
38
71
49
56
13
4
59
96
81
33
7
48
72
60
24
15
73
69
90
82
44
17
58
1
35
26
68
74
9
91
83
55
27
12
46
30
37
8
75
19
92
84
66
23
50
41
14
25
36
40
51
62
3
77
88
99
21
32
43
54
65
6
10
89
97
78
42
53
64
5
16
20
31
98
79
87
1
2
1
1
5
+1
2
1
+
+1
2
+1
0
1
+1
2
1
1
1
1