test


 

Theoretical Computer Science Cheat Sheet
Definitions Series
f(n)=O(g(n)) iff ∃ positive c, n
0
such that
0 ≤ f(n) ≤ cg(n) ∀n ≥ n
0
.
n
i=1
i =
n(n +1)
2
,
n
i=1
i
2
=
n(n + 1)(2n +1)
6
,
n
i=1
i
3
=
n
2
(n +1)
2
4
.
In general:
n
i=1
i
m
=
1
m +1
(n +1)
m+1
− 1 −
n
i=1
(i +1)
m+1
− i
m+1
− (m +1)i
m
n−1
i=1
i
m
=
1
m +1
m
k=0
m +1
k
B
k
n
m+1−k
.
Geometric series:
n
i=0
c
i
=
c
n+1
− 1
c − 1
,c=1,
∞
i=0
c
i
=
1
1 − c
,
∞
i=1
c
i
=
c
1 − c
, |c| < 1,
n
i=0
ic
i
=
nc
n+2
− (n +1)c
n+1
+ c
(c − 1)
2
,c=1,
∞
i=0
ic
i
=
c
(1 − c)
2
, |c| < 1.
Harmonic series:
H
n
=
n
i=1
1
i
,
n
i=1
iH
i
=
n(n +1)
2
H
n
−
n(n − 1)
4
.
n
i=1
H
i
=(n +1)H
n
− n,
n
i=1
i
m
H
i
=
n +1
m +1

H
n+1
−
1
m +1
.
f(n)=Ω(g(n)) iff ∃ positive c, n
0
such that
f(n) ≥ cg(n) ≥ 0 ∀n ≥ n
0
.
f(n)=Θ(g(n)) iff f(n)=O(g(n)) and
f(n)=Ω(g(n)).
f(n)=o(g(n)) iff lim
n→∞
f(n)/g(n)=0.
lim
n→∞
a
n
= a iff ∀>0, ∃n
0
such that
|a
n
− a| <, ∀n ≥ n
0
.
sup S least b ∈ R such that b ≥ s,
∀s ∈ S.
inf S greatest b ∈ R such that b ≤
s, ∀s ∈ S.
lim inf
n→∞
a
n
lim
n→∞
inf{a
i
| i ≥ n, i ∈ N}.
lim sup
n→∞
a
n
lim
n→∞
sup{a
i
| i ≥ n, i ∈ N}.
n
k
Combinations: Size k sub-
sets of a size n set.
n
k
Stirling numbers (1st kind):
Arrangements of an n ele-
ment set into k cycles.
1.
n
k
=
n!
(n − k)!k!
, 2.
n
k=0
n
k
=2
n
, 3.
n
k
=
n
n − k
,
4.
n
k
=
n
k
n − 1
k −1
, 5.
n
k
=
n − 1
k
+
n − 1
k −1
,
6.
n
m

m
k
=
n
k

n − k
m − k
, 7.
n
k=0
r + k
k
=
r + n +1
n
,
8.
n
k=0
k
m
=
n +1
m +1
, 9.
n
k=0
r
k

s
n − k
=
r + s
n
,
10.
n
k
=(−1)
k
k −n −1
k
, 11.
n
1
=
n
n
=1,
12.
n
2
=2
n−1
− 1, 13.
n
k
= k
n − 1
k
+
n − 1
k −1
,
n
k
Stirling numbers (2nd kind):
Partitions of an n element
set into k non-empty sets.
n
k
1st order Eulerian numbers:
Permutations π
1
π
2
...π
n
on
{1, 2,...,n} with k ascents.

n
k

2nd order Eulerian numbers.
C
n
Catalan Numbers: Binary
trees with n + 1 vertices.
14.
n
1
=(n − 1)!, 15.
n
2
=(n − 1)!H
n−1
, 16.
n
n
=1, 17.
n
k
≥
n
k
,
18.
n
k
=(n − 1)
n − 1
k
+
n − 1
k −1
, 19.
n
n − 1
=
n
n − 1
=
n
2
, 20.
n
k=0
n
k
= n!, 21. C
n
=
1
n +1
2n
n
,
22.
n
0
=
n
n − 1
=1, 23.
n
k
=
n
n − 1 − k
, 24.
n
k
=(k +1)
n − 1
k
+(n − k)
n − 1
k −1
,
25.
0
k
=
1ifk =0,
0 otherwise
26.
n
1
=2
n
− n − 1, 27.
n
2
=3
n
− (n + 1)2
n
+
n +1
2
,
28. x
n
=
n
k=0
n
k

x + k
n
, 29.
n
m
=
m
k=0
n +1
k
(m +1− k)
n
(−1)
k
, 30. m!
n
m
=
n
k=0
n
k

k
n − m
,
31.
n
m
=
n
k=0
n
k

n − k
m
(−1)
n−k−m
k!, 32.

n
0

=1, 33.

n
n

= 0 for n =0,
34.

n
k

=(k +1)

n − 1
k

+(2n − 1 − k)

n − 1
k −1

, 35.
n
k=0

n
k

=
(2n)
n
2
n
,
36.
x
x − n
=
n
k=0

n
k

x + n − 1 −k
2n
, 37.
n +1
m +1
=
k
n
k

k
m
=
n
k=0
k
m
(m +1)
n−k
,
 
Theoretical Computer Science Cheat Sheet
Identities Cont. Trees
38.
n +1
m +1
=
k
n
k

k
m
=
n
k=0
k
m
n
n−k
= n!
n
k=0
1
k!
k
m
, 39.
x
x − n
=
n
k=0

n
k

x + k
2n
,
40.
n
m
=
k
n
k

k +1
m +1
(−1)
n−k
, 41.
n
m
=
k
n +1
k +1

k
m
(−1)
m−k
,
42.
m + n +1
m
=
m
k=0
k
n + k
k
, 43.
m + n +1
m
=
m
k=0
k(n + k)
n + k
k
,
44.
n
m
=
k
n +1
k +1

k
m
(−1)
m−k
, 45. (n − m)!
n
m
=
k
n +1
k +1

k
m
(−1)
m−k
, for n ≥ m,
46.
n
n − m
=
k
m − n
m + k

m + n
n + k

m + k
k
, 47.
n
n − m
=
k
m − n
m + k

m + n
n + k

m + k
k
,
48.
n
+ m

+ m
=
k
k

n − k
m

n
k
, 49.
n
+ m

+ m
=
k
k

n − k
m

n
k
.
Every tree with n
vertices has n − 1
edges.
Kraft inequal-
ity: If the depths
of the leaves of
a binary tree are
d
1
,...,d
n
:
n
i=1
2
−d
i
≤ 1,
and equality holds
only if every in-
ternal node has 2
sons.
Recurrences
Master method:
T (n)=aT (n/b)+f (n),a≥ 1,b > 1
If ∃>0 such that f(n)=O(n
log
b
a−
)
then
T (n)=Θ(n
log
b
a
).
If f(n)=Θ(n
log
b
a
) then
T (n)=Θ(n
log
b
a
log
2
n).
If ∃>0 such that f(n)=Ω(n
log
b
a+
),
and ∃c<1 such that af(n/b) ≤ cf(n)
for large n, then
T (n)=Θ(f(n)).
Substitution (example): Consider the
following recurrence
T
i+1
=2
2
i
· T
2
i
,T
1
=2.
Note that T
i
is always a power of two.
Let t
i
= log
2
T
i
. Then we have
t
i+1
=2
i
+2t
i
,t
1
=1.
Let u
i
= t
i
/2
i
. Dividing both sides of
the previous equation by 2
i+1
we get
t
i+1
2
i+1
=
2
i
2
i+1
+
t
i
2
i
.
Substituting we find
u
i+1
=
1
2
+ u
i
,u
1
=
1
2
,
which is simply u
i
= i/2. So we find
that T
i
has the closed form T
i
=2
i2
i−1
.
Summing factors (example): Consider
the following recurrence
T (n)=3T (n/2) + n, T(1) = 1.
Rewrite so that all terms involving T
are on the left side
T (n) −3T (n/2) = n.
Now expand the recurrence, and choose
a factor which makes the left side “tele-
scope”
1
T (n) −3T (n/2) = n
3
T (n/2) −3T (n/4) = n/2
.
.
.
.
.
.
.
.
.
3
log
2
n−1
T (2) −3T (1) = 2
Let m = log
2
n. Summing the left side
we get T (n) − 3
m
T (1) = T (n) − 3
m
=
T (n) − n
k
where k = log
2
3 ≈ 1.58496.
Summing the right side we get
m−1
i=0
n
2
i
3
i
= n
m−1
i=0
3
2
i
.
Let c =
3
2
. Then we have
n
m−1
i=0
c
i
= n
c
m
− 1
c − 1
=2n(c
log
2
n
− 1)
=2n(c
(k−1) log
c
n
− 1)
=2n
k
− 2n,
and so T (n)=3n
k
− 2n. Full history re-
currences can often be changed to limited
history ones (example): Consider
T
i
=1+
i−1
j=0
T
j
,T
0
=1.
Note that
T
i+1
=1+
i
j=0
T
j
.
Subtracting we find
T
i+1
− T
i
=1+
i
j=0
T
j
− 1 −
i−1
j=0
T
j
= T
i
.
And so T
i+1
=2T
i
=2
i+1
.
Generating functions:
1. Multiply both sides of the equa-
tion by x
i
.
2. Sum both sides over all i for
which the equation is valid.
3. Choose a generating function
G(x). Usually G(x)=
∞
i=0
x
i
g
i
.
3. Rewrite the equation in terms of
the generating function G(x).
4. Solve for G(x).
5. The coefficient of x
i
in G(x)isg
i
.
Example:
g
i+1
=2g
i
+1,g
0
=0.
Multiply and sum:
i≥0
g
i+1
x
i
=
i≥0
2g
i
x
i
+
i≥0
x
i
.
We choose G(x)=
i≥0
x
i
g
i
. Rewrite
in terms of G(x):
G(x) − g
0
x
=2G(x)+
i≥0
x
i
.
Simplify:
G(x)
x
=2G(x)+
1
1 − x
.
Solve for G(x):
G(x)=
x
(1 − x)(1 − 2x)
.
Expand this using partial fractions:
G(x)=x
2
1 − 2x
−
1
1 − x
= x
2
i≥0
2
i
x
i
−
i≥0
x
i
=
i≥0
(2
i+1
− 1)x
i+1
.
So g
i
=2
i
− 1.
 
Theoretical Computer Science Cheat Sheet
π ≈ 3.14159, e ≈ 2.71828, γ ≈ 0.57721, φ =
1+
√
5
2
≈ 1.61803,
ˆ
φ =
1−
√
5
2
≈−.61803
i 2
i
p
i
General Probability
1 2 2
Bernoulli Numbers (B
i
=0,oddi = 1):
B
0
=1,B
1
= −
1
2
, B
2
=
1
6
, B
4
= −
1
30
,
B
6
=
1
42
, B
8
= −
1
30
, B
10
=
5
66
.
Change of base, quadratic formula:
log
b
x =
log
a
x
log
a
b
,
−b ±
√
b
2
− 4ac
2a
.
Euler’s number e:
e =1+
1
2
+
1
6
+
1
24
+
1
120
+ ···
lim
n→∞
1+
x
n
n
= e
x
.
1+
1
n
n
<e<
1+
1
n
n+1
.
1+
1
n
n
= e −
e
2n
+
11e
24n
2
− O
1
n
3
.
Harmonic numbers:
1,
3
2
,
11
6
,
25
12
,
137
60
,
49
20
,
363
140
,
761
280
,
7129
2520
,...
ln n<H
n
< ln n +1,
H
n
=lnn + γ + O
1
n
.
Factorial, Stirling’s approximation:
1, 2, 6, 24, 120, 720, 5040, 40320, 362880, ...
n!=
√
2πn
n
e
n
1+Θ
1
n

.
Ackermann’s function and inverse:
a(i, j)=
2
j
i =1
a(i − 1, 2) j =1
a(i − 1,a(i, j − 1)) i, j ≥ 2
α(i) = min{j | a(j, j) ≥ i}.
Continuous distributions: If
Pr[a<X<b]=
b
a
p(x) dx,
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 exist then
P (a)=
a
−∞
p(x) dx.
Expectation: If X is discrete
E
[g(X)] =
x
g(x)Pr[X = x].
If X continuous then
E
[g(X)] =
∞
−∞
g(x)p(x) dx =
∞
−∞
g(x) dP(x).
Variance, standard deviation:
VAR[X]=
E
[X
2
] −
E
[X]
2
,
σ =
VAR[X].
For events A and B:
Pr[A ∨ B] = Pr[A] + Pr[B] − Pr[A ∧ B]
Pr[A ∧ B] = Pr[A] · Pr[B],
iff A and B are independent.
Pr[A|B]=
Pr[A ∧ B]
Pr[B]
For random variables X and Y :
E
[X · Y ]=
E
[X] ·
E
[Y ],
if X and Y are independent.
E
[X + Y ]=
E
[X]+
E
[Y ],
E
[cX]=c
E
[X].
Bayes’ theorem:
Pr[A
i
|B]=
Pr[B|A
i
]Pr[A
i
]
n
j=1
Pr[A
j
]Pr[B|A
j
]
.
Inclusion-exclusion:
Pr
n
i=1
X
i
=
n
i=1
Pr[X
i
]+
n
k=2
(−1)
k+1
i
i
<···<i
k
Pr
k
j=1
X
i
j
.
Moment inequalities:
Pr
|X|≥λ
E
[X]
≤
1
λ
,
Pr
X −
E
[X]
≥ λ · σ
≤
1
λ
2
.
Geometric distribution:
Pr[X = k]=pq
k−1
,q=1−p,
E
[X]=
∞
k=1
kpq
k−1
=
1
p
.
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
Binomial distribution:
Pr[X = k]=
n
k
p
k
q
n−k
,q=1−p,
E
[X]=
n
k=1
k
n
k
p
k
q
n−k
= np.
Poisson distribution:
Pr[X = k]=
e
−λ
λ
k
k!
,
E
[X]=λ.
Normal (Gaussian) distribution:
p(x)=
1
√
2πσ
e
−(x−µ)
2
/2σ
2
,
E
[X]=µ.
The “coupon collector”: We are given a
random coupon each day, and there are n
different types of coupons. The distribu-
tion of coupons is uniform. The expected
number of days to pass before we to col-
lect all n types is
nH
n
.
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
 
Theoretical Computer Science Cheat Sheet
Trigonometry Matrices More Trig.
A
c
θ
B
a
b
C
(0,-1)
(0,1)
(-1,0) (1,0)
(cos θ, sin θ)
Pythagorean theorem:
C
2
= A
2
+ B
2
.
Definitions:
sin a = A/C, cos a = B/C,
csc a = C/A, sec a = C/B,
tan a =
sin a
cos a
=
A
B
, cot a =
cos a
sin a
=
B
A
.
Area, radius of inscribed circle:
1
2
AB,
AB
A + B + C
.
Identities:
sin x =
1
csc x
, cos x =
1
sec x
,
tan x =
1
cot x
, sin
2
x + cos
2
x =1,
1 + tan
2
x = sec
2
x, 1 + cot
2
x = csc
2
x,
sin x = cos
π
2
− x
, sin x = sin(π − x),
cos x = −cos(π −x), tan x = cot
π
2
− x
,
cot x = −cot(π −x), csc x = cot
x
2
− cot x,
sin(x ± y) = sin x cos y ± cos x sin y,
cos(x ± y) = cos x cos y ∓ sin x sin y,
tan(x ± y)=
tan x ± tan y
1 ∓ tan x tan y
,
cot(x ± y)=
cot x cot y ∓ 1
cot x ± cot y
,
sin 2x = 2 sin x cos x, sin 2x =
2 tan x
1 + tan
2
x
,
cos 2x = cos
2
x − sin
2
x, cos 2x = 2 cos
2
x − 1,
cos 2x =1− 2 sin
2
x, cos 2x =
1 − tan
2
x
1 + tan
2
x
,
tan 2x =
2 tan x
1 − tan
2
x
, cot 2x =
cot
2
x − 1
2 cot x
,
sin(x + y) sin(x − y) = sin
2
x − sin
2
y,
cos(x + y) cos(x − y) = cos
2
x − sin
2
y.
Euler’s equation:
e
ix
= cos x + i sinx, e
iπ
= −1.
Multiplication:
C = A · B, c
i,j
=
n
k=1
a
i,k
b
k,j
.
Determinants: det A =0iffA is non-singular.
det A · B = det A ·detB,
det A =
π
n
i=1
sign(π)a
i,π(i)
.
2 × 2 and 3 × 3 determinant:
ab
cd
= ad − bc,
abc
def
ghi
= g
bc
ef
− h
ac
df
+ i
ab
de
=
aei + bfg + cdh
− ceg −fha− ibd.
Permanents:
perm A =
π
n
i=1
a
i,π(i)
.
A
a
c
h
b
B
C
Law of cosines:
c
2
= a
2
+b
2
−2ab cos C.
Area:
A =
1
2
hc,
=
1
2
ab sin C,
=
c
2
sin A sin B
2 sin C
.
Heron’s formula:
A =
√
s · s
a
· s
b
· s
c
,
s =
1
2
(a + b + c),
s
a
= s − a,
s
b
= s − b,
s
c
= s − c.
More identities:
sin
x
2
=
1 − cos x
2
,
cos
x
2
=
1 + cos x
2
,
tan
x
2
=
1 − cos x
1 + cos x
,
=
1 − cos x
sin x
,
=
sin x
1 + cos x
,
cot
x
2
=
1 + cos x
1 − cos x
,
=
1 + cos x
sin x
,
=
sin x
1 − cos x
,
sin x =
e
ix
− e
−ix
2i
,
cos x =
e
ix
+ e
−ix
2
,
tan x = −i
e
ix
− e
−ix
e
ix
+ e
−ix
,
= −i
e
2ix
− 1
e
2ix
+1
,
sin x =
sinh ix
i
,
cos x = cosh ix,
tan x =
tanh ix
i
.
Hyperbolic Functions
Definitions:
sinh x =
e
x
− e
−x
2
, cosh x =
e
x
+ e
−x
2
,
tanh x =
e
x
− e
−x
e
x
+ e
−x
, csch x =
1
sinh x
,
sech x =
1
cosh x
, coth x =
1
tanh x
.
Identities:
cosh
2
x − sinh
2
x =1, tanh
2
x + sech
2
x =1,
coth
2
x − csch
2
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
2
x + sinh
2
x,
cosh x + sinh x = e
x
, cosh x −sinh x = e
−x
,
(cosh x + sinh x)
n
= cosh nx + sinh nx, n ∈ Z,
2 sinh
2
x
2
= cosh x − 1, 2 cosh
2
x
2
= cosh x +1.
θ sin θ cos θ tan θ
00 1 0
π
6
1
2
√
3
2
√
3
3
π
4
√
2
2
√
2
2
1
π
3
√
3
2
1
2
√
3
π
2
10∞
...in mathematics
you don’t under-
stand things, you
just get used to
them.
– J. von Neumann
v2.02
c
1994 by Steve Seiden
sseiden@acm.org
http://www.csc.lsu.edu/~seiden
 
Theoretical Computer Science Cheat Sheet
Number Theory Graph Theory
The Chinese remainder theorem: There ex-
ists a number C such that:
C ≡ r
1
mod m
1
.
.
.
.
.
.
.
.
.
C ≡ r
n
mod m
n
if m
i
and m
j
are relatively prime for i = j.
Euler’s function: φ(x) is the number of
positive integers less than x relatively
prime to x.If
n
i=1
p
e
i
i
is the prime fac-
torization of x then
φ(x)=
n
i=1
p
e
i
−1
i
(p
i
− 1).
Euler’s theorem: If a and b are relatively
prime then
1 ≡ a
φ(b)
mod b.
Fermat’s theorem:
1 ≡ a
p−1
mod p.
The Euclidean algorithm: if a>bare in-
tegers then
gcd(a, b) = gcd(a mod b, b).
If
n
i=1
p
e
i
i
is the prime factorization of x
then
S(x)=
d|x
d =
n
i=1
p
e
i
+1
i
− 1
p
i
− 1
.
Perfect Numbers: x is an even perfect num-
ber iff x =2
n−1
(2
n
−1) and 2
n
−1 is prime.
Wilson’s theorem: n is a prime iff
(n − 1)! ≡−1modn.
M¨obius inversion:
µ(i)=
1ifi =1.
0ifi is not square-free.
(−1)
r
if i is the product of
r distinct primes.
If
G(a)=
d|a
F (d),
then
F (a)=
d|a
µ(d)G
a
d
.
Prime numbers:
p
n
= n ln n + nln ln n − n + n
ln ln n
ln n
+ O
n
ln n
,
π(n)=
n
ln n
+
n
(ln n)
2
+
2!n
(ln n)
3
+ O
n
(ln n)
4
.
Definitions:
Loop An edge connecting a ver-
tex to itself.
Directed Each edge has a direction.
Simple Graph with no loops or
multi-edges.
Walk A sequence v
0
e
1
v
1
...e
v
.
Trail A walk with distinct edges.
Path A trail with distinct
vertices.
Connected A graph where there exists
a path between any two
vertices.
Component A maximal connected
subgraph.
T ree A connected acyclic graph.
F ree tree A tree with no root.
DAG Directed acyclic graph.
Eulerian Graph with a trail visiting
each edge exactly once.
Hamiltonian Graph with a cycle visiting
each vertex exactly once.
Cut A set of edges whose re-
moval increases the num-
ber of components.
Cut-set A minimal cut.
Cut edge A size 1 cut.
k-Connected A graph connected with
the removal of any k − 1
vertices.
k-Tough ∀S ⊆ V,S = ∅ we have
k ·c(G − S) ≤|S|.
k-Regular A graph where all vertices
have degree k.
k-Factor A k-regular spanning
subgraph.
Matching A set of edges, no two of
which are adjacent.
Clique A set of vertices, all of
which are adjacent.
Ind. set A set of vertices, none of
which are adjacent.
Vertex cover A set of vertices which
cover all edges.
Planar graph A graph which can be em-
beded in the plane.
Plane graph An embedding of a planar
graph.
v∈V
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 de-
gree ≤ 5.
Notation:
E(G) Edge set
V (G) Vertex set
c(G) Number of components
G[S] Induced subgraph
deg(v) Degree of v
∆(G) Maximum degree
δ(G) Minimum degree
χ(G) Chromatic number
χ
E
(G) Edge chromatic number
G
c
Complement graph
K
n
Complete graph
K
n
1
,n
2
Complete bipartite graph
r
(k, ) Ramsey number
Geometry
Projective coordinates: triples
(x, y, z), not all x, y and z zero.
(x, y, z)=(cx, cy, cz) ∀c =0.
Cartesian Projective
(x, y)(x, y, 1)
y = mx + b (m, −1,b)
x = c (1, 0, −c)
Distance formula, L
p
and L
∞
metric:
(x
1
− x
0
)
2
+(y
1
− y
0
)
2
,
|x
1
− x
0
|
p
+ |y
1
− y
0
|
p
1/p
,
lim
p→∞
|x
1
− x
0
|
p
+ |y
1
− y
0
|
p
1/p
.
Area of triangle (x
0
,y
0
), (x
1
,y
1
)
and (x
2
,y
2
):
1
2
abs
x
1
− x
0
y
1
− y
0
x
2
− x
0
y
2
− y
0
.
Angle formed by three points:
θ
(0, 0)
(x
1
,y
1
)
(x
2
,y
2
)
2
1
cos θ =
(x
1
,y
1
) · (x
2
,y
2
)
1
2
.
Line through two points (x
0
,y
0
)
and (x
1
,y
1
):
xy1
x
0
y
0
1
x
1
y
1
1
=0.
Area of circle, volume of sphere:
A = πr
2
,V=
4
3
πr
3
.
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
π Calculus
Wallis’ identity:
π =2·
2 · 2 · 4 · 4 ·6 ·6 ···
1 · 3 · 3 · 5 ·5 ·7 ···
Brouncker’s continued fraction expansion:
π
4
=1+
1
2
2+
3
2
2+
5
2
2+
7
2
2+···
Gregrory’s series:
π
4
=1−
1
3
+
1
5
−
1
7
+
1
9
−···
Newton’s series:
π
6
=
1
2
+
1
2 · 3 · 2
3
+
1 · 3
2 · 4 · 5 · 2
5
+ ···
Sharp’s series:
π
6
=
1
√
3
1 −
1
3
1
· 3
+
1
3
2
· 5
−
1
3
3
· 7
+ ···
Euler’s series:
π
2
6
=
1
1
2
+
1
2
2
+
1
3
2
+
1
4
2
+
1
5
2
+ ···
π
2
8
=
1
1
2
+
1
3
2
+
1
5
2
+
1
7
2
+
1
9
2
+ ···
π
2
12
=
1
1
2
−
1
2
2
+
1
3
2
−
1
4
2
+
1
5
2
−···
Derivatives:
1.
d(cu)
dx
= c
du
dx
, 2.
d(u + v)
dx
=
du
dx
+
dv
dx
, 3.
d(uv)
dx
= u
dv
dx
+ v
du
dx
,
4.
d(u
n
)
dx
= nu
n−1
du
dx
, 5.
d(u/v)
dx
=
v
du
dx
− u
dv
dx
v
2
, 6.
d(e
cu
)
dx
= ce
cu
du
dx
,
7.
d(c
u
)
dx
= (ln c)c
u
du
dx
, 8.
d(ln u)
dx
=
1
u
du
dx
,
9.
d(sin u)
dx
= cos u
du
dx
, 10.
d(cos u)
dx
= −sin u
du
dx
,
11.
d(tan u)
dx
= sec
2
u
du
dx
, 12.
d(cot u)
dx
= csc
2
u
du
dx
,
13.
d(sec u)
dx
= tan u sec u
du
dx
, 14.
d(csc u)
dx
= −cot u csc u
du
dx
,
15.
d(arcsin u)
dx
=
1
√
1 − u
2
du
dx
, 16.
d(arccos u)
dx
=
−1
√
1 − u
2
du
dx
,
17.
d(arctan u)
dx
=
1
1+u
2
du
dx
, 18.
d(arccot u)
dx
=
−1
1+u
2
du
dx
,
19.
d(arcsec u)
dx
=
1
u
√
1 − u
2
du
dx
, 20.
d(arccsc u)
dx
=
−1
u
√
1 − u
2
du
dx
,
21.
d(sinh u)
dx
= cosh u
du
dx
, 22.
d(cosh u)
dx
= sinh u
du
dx
,
23.
d(tanh u)
dx
= sech
2
u
du
dx
, 24.
d(coth u)
dx
= −csch
2
u
du
dx
,
25.
d(sech u)
dx
= −sech u tanh u
du
dx
, 26.
d(csch u)
dx
= −csch u coth u
du
dx
,
27.
d(arcsinh u)
dx
=
1
√
1+u
2
du
dx
, 28.
d(arccosh u)
dx
=
1
√
u
2
− 1
du
dx
,
29.
d(arctanh u)
dx
=
1
1 − u
2
du
dx
, 30.
d(arccoth u)
dx
=
1
u
2
− 1
du
dx
,
31.
d(arcsech u)
dx
=
−1
u
√
1 − u
2
du
dx
, 32.
d(arccsch u)
dx
=
−1
|u|
√
1+u
2
du
dx
.
Integrals:
1.
cu dx = c
u dx, 2.
(u + v) dx =
udx+
v dx,
3.
x
n
dx =
1
n +1
x
n+1
,n= −1, 4.
1
x
dx =lnx, 5.
e
x
dx = e
x
,
6.
dx
1+x
2
= arctan x, 7.
u
dv
dx
dx = uv −
v
du
dx
dx,
8.
sin xdx= −cos x, 9.
cos xdx= sin x,
10.
tan xdx= −ln |cos x|, 11.
cot xdx=ln|cos x|,
12.
sec xdx=ln|sec x + tan x|, 13.
csc xdx=ln|csc x + cotx|,
14.
arcsin
x
a
dx = arcsin
x
a
+
a
2
− x
2
,a>0,
Partial Fractions
Let N(x) and D(x) be polynomial func-
tions of x. We can break down
N(x)/D(x) using partial fraction expan-
sion. First, if the degree of N is greater
than or equal to the degree of D, divide
N by D, obtaining
N(x)
D(x)
= Q(x)+
N
(x)
D(x)
,
where the degree of N
is less than that of
D. Second, factor D(x). Use the follow-
ing rules: For a non-repeated factor:
N(x)
(x − a)D(x)
=
A
x − a
+
N
(x)
D(x)
,
where
A =
N(x)
D(x)
x=a
.
For a repeated factor:
N(x)
(x − a)
m
D(x)
=
m−1
k=0
A
k
(x − a)
m−k
+
N
(x)
D(x)
,
where
A
k
=
1
k!
d
k
dx
k
N(x)
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
 
 
 
 
 
 
 

未分类 Comments(0) 2015年5月01日 13:38

OMG English study note

nothing better

  • nothing cool me down better than ine-cream
  • nothing put me to sleep better than classical music.
  • nothing wakes me up better than coffee.

date night romance

  • Go on the date (約會愛情)
  • kiss and tell(揭露隱私)
  • play hard to get(女孩喜歡某男孩,但故作不願讓其接近狀)

未分类 english_study OMG Comments(1) 2011年8月26日 22:48

人民日报，你想干什么(转载)

人民日报，你想干什么 / 贾葭

  文章写的很好,原链接已经失效,特地转载于此.

人民日报，你想干什么

贾葭

　　6月1日，谷歌公司有关负责人在博客上称，该公司数百名邮件用户受到“网络钓鱼”攻击，黑客来自中国济南，受影响的包括一些美国政府官员、“中国人权活动人士”及外国记者等的邮箱。

《人民日报》于6月6日刊出题为《谷歌，你想干什么》的文章，称谷歌诽谤中国。

事实上，这已经不是《人民日报》第一次诽谤谷歌了。

2009年6月18日，中央电视台称谷歌传播淫秽色情图片，并命令自己的实习生现身说法，称自己看了谷歌网站之后“心神不宁”，成为当年的中国第二大笑话。《人民日报》、央视等官方媒体自此不遗余力地污蔑谷歌。

2010年3月24日，《人民日报》又刊出《谷歌不是上帝》的文章，对已经退出中国市场的谷歌搜索引擎穷追猛打。这种行为有意迎合中国政府对西方世界的负面想象，强烈暗示谷歌是美国政府的爪牙，但是他们没能提供任何证据。由此看来，《人民日报》将指责的矛头指向谷歌，是无中生有、别有用心、意图险恶的。

因为，中国早有建立大中华局域网的计划，已经建立了威力强大的功夫网以及相关过滤及拦截系统。谷歌的“不作恶”的理念及不配合的态度，让中国的互联网高墙 的墙角有些缺憾。如果真的认为谷歌有问题，可以诉诸司法解决，何以一而再、再而三地抹黑谷歌，利用舆论高唱谷歌威胁论？

　 《人民日报》的这些指控非常严重，已经严重到不像一份宣传纸的正常态度了。

更耐人寻味的是，美国国防部最近拟定了首个正式网络战略，称将把来自另一个国家的一切针对美国的“网络入侵行为”划分等级，其中，最高等级的网络入侵将 被视作“战争行为”。不少国际观察人士认为，《人民日报》的指控具有极浓的政治色彩，不排除它有借机挑起新的中美互联网安全争端的险恶意图，为中国的网络战略找靶子。

如今的《人民日报》让人扼腕。曾经领衔宣传思想阵地的第一面旗帜，已经沦为诽谤他国企业的政治工具；它曾经是领唱自由民主人权的旧《新华日报》，如今却背弃了它早年倡导过的理念。

其实，《人民日报》不应该过多卷入政治斗争、充当政治博弈工具，一旦国内风云有变，恐怕会成为政治牺牲的对象，也将继续被市场抛弃。

在无数的中国传媒机构里，党化报纸、人渣记者大量存在。《人民日报》刊出这样的文章恐怕是难免的。其实，中国是世界上报纸杂志最多的国家之一，来自中国国家新闻出版总署的数据表明，2010年，中国境内共有9000多家报章杂志。有六分之一的媒体依赖市场而运营，而《人民日报》却完全依赖行政命令强行派发。

作为国内知名的传声筒，《人民日报》应该顺应历史发展规律，重树传媒精神，做一个青史留美名、世人都尊敬的报纸，继续走在传媒创新的大道上，而不要被路边的荆棘砾石绊住，更不要被海妖塞壬的美妙歌声所诱惑。

　　（作者为无业游民）

 

 

原文：

 

 

 

谷歌，你想干什么(望海楼)

 

张意轩

 

《 人民日报海外版 》（ 2011年06月06日 第 01 版）

　　6月1日，谷歌公司有关负责人在博客上称，该公司数百名邮件用户受到“网络钓鱼”攻击，黑客来自中国济南，受影响的包括一些美国政府官员、“中国人权活动人士”及外国记者等的邮箱。

 

　　事实上，这已经不是谷歌第一次诽谤中国了。

 

　 　去年1月，谷歌就声称“受到来自中国黑客的攻击”，但至今仍未能拿出任何证据；这回，谷歌将“中国人权活动人士”列入受害者名单内，有意迎合西方世界对 中国政府的负面想象，强烈暗示黑客攻击是中国政府指使干的，但依然没有公布发现来自中国境内黑客攻击的证据。由此看来，谷歌将指责的矛头指向中国，是无中 生有、别有用心、意图险恶的。

 

　　因为，中美之间早有打击黑客等网络犯罪的国际合作，已经建立了司法领域的国际合作机制。谷歌若掌握实据，可以诉诸司法解决，何以一而再、再而三地抹黑中国，利用舆论高唱中国威胁论？

 

　　谷歌的这些指控非常严重，美国联邦调查局正在与谷歌一起展开调查。

 

　 　更耐人寻味的是，美国国防部最近拟定了首个正式网络战略，称将把来自另一个国家的一切针对美国的“网络入侵行为”划分等级，其中，最高等级的网络入侵将 被视作“战争行为”，可以使用传统军事力量予以报复回击。不少国际观察人士认为，谷歌的所谓指控具有极浓的政治色彩，不排除它有借机挑起新的中美互联网安 全争端的险恶意图，为美国的网络战略找靶子。

 

　　如今的谷歌让人扼腕。曾经领衔创新的互联网标杆，已经沦为诽谤它国的政治工具；曾经领唱开放共享平等的领袖企业，如今却背弃了互联网精神。

 

　　其实，谷歌不应该过多卷入国际政治斗争、充当政治博弈工具，一旦国际风云有变，恐怕会成为政治牺牲的对象，也将会被市场抛弃。

 

　 　在无序的互联网上，商业间谍、网络黑客大量存在，谷歌遭受网络攻击恐怕是难免的。其实，中国是世界上遭受网络攻击最多的国家之一，来自中国国家互联网应 急中心的数据表明，2010年，中国境内共有451万余个IP地址的主机被植入木马，比2009年增长了1620.3%；2010年，境外木马控制服务器 IP数量约有22万个，2009年增长了34.1%，其中位于美国的最多，占14.66%，较2009年增长57%。

 

　　作为国际知名的互联网企业，谷歌应该顺应互联网发展规律，重树互联网精神，做一个青史留美名、世人都尊敬的企业，继续走在创新的大道上，而不要被路边的荆棘砾石绊住，更不要被海妖塞壬的美妙歌声所诱惑。

 

　　（作者为本报编辑）

未分类 Comments(2) 2011年6月08日 01:46