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

《牛津高阶英汉双解词典》的语法标识

C——可数名词
U——不可数名词
CGp——可数集合名词
Gp——-集合名词
sing v——单数动词(如lives)
pl v——复数动词 (l如ive)
sing or pl v--单数动词或复数动词
pl——复数名词
sing——单数名词
attrib——用作定语
pred——用作表语
La——系动词+形容词
Ln——系动词+名词
I——不及物动词
Ipr——不及物动词+介词短语
Ip——不及物动词+副词小词
In/pr——不及物动词+名词/介词短语
It——不及物动词+带to的不定式
Tn——及物动词+名词
Tn.pr——及物动词+名词+介词短语
Tn.p——及物动词+名词+副词小词
Tf——及物动词+限定式that从句
Tw——及物动词+从句或短语
Tt——及物动词+带to的不定式
Tnt——及物动词+名词+带to的不定式
Tg——及物动词+动词-ing成分
TSg——及物动词+名词（’s）+动词-ing成分
Tng——及物动词+名词+动词-ing成分
Tni——及物动词+名词+不带to的不定式
Cn.a——复合及物动词+名词+形容词
Cn.n——复合及物动词+名词+名词
Cn.n/a——复合及物动词+名词+名词或形容词
Cn.t——复合及物动词+名词+带to的不定式
Cn.g——复合及物动词+名词+动词-ing成分
Cn.i——复合及物动词+名词+不带to的不定式
Dn.n——双及物动词++名词+名词
Dn.pr——双及物动词+名词+介词短语
Dn.f——双及物动词+名词+限定式that从句
Dpr.f——双及物动词+介词短语+限定式that从句
Dn.w——双及物动词+名词+wh-从句或短语
Dpr.w——双及物动词+介词短语+从句或短语
Dn.t——双及物动词+名词+带to的不定式
Dpr.t——双及物动词+介词短语+带to的不定式

可能有错误望指出.

english english Comments(6) 2011年8月21日 18:19

How to convert mindmanager to freemind

Recently ,I encounter a problem that how to convert mindmanager to freemind in Ubuntu .By searching in internet,I find a effective method to solve this problem,using python script below .
http://www.liberatedcomputing.net/mm2fm/scripts/mm2fm
Maybe you have not install libxslt module in your computer ,so you should install it firstly.
    

sudo apt-get install python-libxslt1

Then,

 chmod +x mm2fm

This script syntax is

 mm2fm FILENAME

It is simple to use.

linux Ubuntu Comments(11) 2011年8月15日 18: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

杨奎松：暴力土改及其原因 （轉載）

好久沒有寫bolg了，轉載一篇文章，原文已被刪除。該文最早見於黑五類第二期。講的是上個世紀五十年代的土地改，現代人知道的已經很少了。是楊奎松教授所寫。也算是奇文共賞吧。

 

 

据 1950年春的新华社《内部参考》，河南省一些地方的土改颇为极端，搞四追（追亲戚、朋友、佃户、狗腿子）五挖（挖夹墙、地洞、粪坑、竹园、稻垛）。干部 权力无边，为所欲为，动辄打骂，仅一个多月就打死、逼死人命30余条。兰封县瓜营区20天内接连逼死7人。该区区长某日到村上开群众大会，一区干部看到有 位中农在家装麦子，便怀疑是地主乘机偷偷隐藏麦子，遂将其拖到会场。区长当场打耳光，并挥枪威胁。七八个区干部见状，也动手乱打。有的干部甚至用枪托乱 捣，以致意外走火，当即打死了坐在台下的村农会主任的母亲。考城城关区未营村佃户宋二妮，一向表现积极，被人诬告是地主走狗，该区副区长不加调查就在群众 大会上指名大骂。其子要求为父申辩，该副区长大发雷霆，将其赶走。宋之子回家后愤而自杀。

　　1950年6月朝鲜战争爆发，特别是10月间志愿军入朝作战，对中国政治产生了巨大冲击。陶铸后来说：中共中央过去主张土改要温和 一点，那是因为战争没有了，搞得太激烈了社会震动太大，不利于统战。现在抗美援朝战争打响了，战争的震动那样大，我们正好可以着手解决国内镇反和土改的问 题了（不用担心动静弄得太大）。10月中下旬以后，毛泽东开始放手在全国推动镇反。11月，毛又全力督促广东、广西、福建等省立即开展全面的土改斗争。

　　中共华东局一向注意反对左倾偏向，这时也开始强调放手。于是，江浙各地土改中迅速出现乱捕、乱斗、乱打倾向。苏南奉贤、浙江嘉兴等 地都有被吊打、罚跪的情形，或把大批地主看管起来。无锡一县遭跪、冻、打的有872人，青浦县龙固区几天里就打死17人。奉贤县5个区被斗的245人中， 被打的218人，被迫下跪的75人，被棒打的35人，被吊打的13人，被捆绑的18人，被剥光衣服的80人，每个人都受多种体罚。宜兴县强迫斗争对象跪碗 底，把猫放入斗争对象裤兜里，剪掉妇女的头发和眉毛。常熟县还发生了割掉被斗妇女乳头的事情。苏南各县（市）土改期间召开村或联合村斗争会16841次， 乡以上斗争会13609次，斗争人数达28234人。苏南区土改期间，仅斗争会上就打死了几十人，并造成293人自杀。

　　西北局因为有1947年土改过火的教训，加上西北地区不少地方没有地主，因此一直也比较谨慎。这时也出现了几乎相同的情况。平利县 四区双河乡对地主、富农、中农以及工商业者40余户进行了全面清算和罚没，连茶缸都不放过。长安乡王曲区斗争地主富农，打、跪、拔胡子、脱衣服已成习惯。 据渭南县九区一市统计，土改干部乱施刑罚，疲劳审讯逼供，逼死地主7人，普通农民15人，富农、小商贩、干部及小土地经营者各一人，造成上吊、跳井、自刎 81人。镇安县分了富农的土地，竹林管区征收了半地主式富农的自耕地。石泉县7个乡斗了43名旧保甲人员，并把他们和地主集中起来强制劳动。南郑58个 乡，半数地主成分者被打，自杀了96人。安康县惩治地主661人，管制357人，自杀82人。紫阳县一度将地主几乎全部管制起来。

　　和华东、西北相比，中南局明显走得更远。它一上来就明确提出：此前的土改试点地区普遍因为防左、纠左太多而存在着"和平土改"的偏 向，造成了严重的"夹生饭"现象，因此必须让干部了解，土改不是单纯分田和得到经济果实，土改的根本目的是要"使土改后的农村真正成为新民主主义人民民主 专政的乡村"。为此，不能束手束脚，"不要过早和过分地强调防左"，不要让群众感觉规矩太多，对真正群众大动起来发生的过火行为，不应泼冷水。总之，要 搞"斗争土改"，"放手发动群众，掀起一个大规模的农民反封建的革命运动"。

　　由于公开强调要敢于放手，并尖锐地提出了反对"和平分田"，中南各省党政部门层层贯彻，一些一直感到束手束脚的基层土改干部，尤其 是军队和农民出身的土改干部，自然容易变得十分激进。湖北潜江重点乡李家大台、紫月两村，共413户，工作队进驻后，硬是划了64户地主，69户富农，地 富合计占总户数32.2%。他们还将这几十家所谓的地主（其中多户实为富农）扫地出门，迫使其全家外出讨饭求生。其他的富农（实为中农和贫农）亦多被剥夺 财产，只是没有被逐出家门而已。汉川县土改工作团亦大张旗鼓地斗地主、打恶霸，全县土改、镇反先后杀了数百地富及反革命分子。其做法之简单激烈，导致了普 遍的恐慌情绪，许多并无多少劣迹的地主富农，甚至一般农民，纷纷自杀。十一区3个多月有37人自杀身亡，三区亦在同样时间里自杀了31人，且多为女性。

　　中原各地陆续开始土改之际，四川省尚处在退押反霸斗争中。双流县1951年初的两个月就枪毙了497人，141人（73男，68 女）因恐惧被斗、被逼而选择自杀。郫县头两个多月枪毙了562人，222人以自杀相抗。不少地主甚至舍命不舍财，宁愿全家自杀也决不肯拱手交出财产。双流 县自杀的141人当中，舍命不舍财的地主就有63人之多。随着土改开始，一些干部更习惯性地把上级号召的"政治上打垮"理解为一个"打"字，"因而在斗争 中产生放任、暗示和组织打人的情况"。"有的还带上打手，以捆、吊、打人代替政治上的打倒地主，阳奉阴违，报喜不报忧，在赔罚、镇反、划成分等各个环节上 交待政策、分别对待不够。有的地方经领导上具体指出来的问题，亦未实际的去做，因而在各个环节上死了一些人，结果大多报为畏罪自杀。"营山县30%的村子 发生了吊打和肉刑，全县被划地主多达3760户，其中自杀了261人（总共自杀301人）。荣昌县七区4个乡，54个村，共划地主663户，3376人。 区领导自土改开始，便放手组织乱打乱吊。14村共划中小地主15户，打死15人，平均每家一个。土改干部林成云在斗争大会上甚至用刀割断了被斗地主的脖 子，众目睽睽下当场将地主杀死。由于地主成为受辱和死亡的代名词，一些农户得知被划为地主后，竟绝望自尽。有地主生怕被斗，硬被拉到斗争会场后，即当场以 头撞柱而死。仅这几个乡地主富农就自杀了96人（男39，女57），当场斗死16人（男9，女7）；斗争后几天里又病死、饿死了66人（男42，女 24），加上关押致死的12人（男8，女4），总共死了190人（男98，女92）。

　　广东东江惠阳县潼湖区欣乐乡土改伊始就乱打乱吊地主，乱挖底财。该区发明了20种吊打人的方法来逼底财。5月30日至6月5日6天 中，打死6人，逼死13人。增城斗争地主中实行吊、打、绑、埋（埋至颈）、关5种办法，还动用火刑，强迫农民签名参加吊打，否则不分果实。惠阳县因此自杀 了199人。仅5－8月间，北江地区就造成614人自杀。潮汕专区则造成755人自杀。兴梅专区仅5月20日至6月7日就逼死202人。全省5－8月连打 死带自杀，共死亡4000人左右。东江地区在1951年上半年土改开始的几个月时间里就斗争了5698人，其中地主成分者2567人，富农成份者1047 人，镇压了其中的3642人，另有2690人因绝望和恐惧自行了断生命。

　　对于已经如此激烈的土改运动，中南局仍批评土改太和平了。经中共中央同意，陶铸等被调到广东，撤换了"在农民问题上犯了右倾错误" 的华南分局领导人方方，并从各地补派了1000名土改干部。新一轮土改从1952年春夏开始，几个月时间就造成了更大范围的伤害。大批过去多少受到保护的 华侨被打成地主、富农，许多人被剥夺了财产。惠阳潼湖区欣乐乡又捉地主100人，使用肉刑打、吊、焗烟、灌水，用木棍自胸至腹碾出大便。博罗有用小蛇、大 蚂蚁装进地主裤裆，还有吊乳头、熏烟火、坐水牢、睡勒床、点天灯、假枪毙等刑讯方法。东莞290人自杀，230人是地主成分。仅恩平一县，在这一轮土改中 因重划阶级就多划了地主1039户，按政策标准等于错划了将近三分之一，也因此错斗1173户，2179人，错捕了486户，553人，被吊打138 户，278人，因错打、错捕、错斗、错管制致死122户，236人，错戴帽子213户，401人，并导致830人自杀，其中地主达570人，富农108 人，有的全家7口全部自杀。另据华南分局通报，从2月3日至3月6日一个月左右的时间里，因为残酷吊打，一度竟造成805人自杀的惨剧，全区这段时间先后 自杀了1165人。在这一阶段土改运动期间，广东全省农村不算被镇压的，光是自杀就死了17000人之多。

　　类似的情况在各地档案中有太多的记载，仅此即不难看出，1950年，特别是抗美援朝战争以后开始的南方和西北地区的土改运动中，过 度暴力和对富农的严重伤害，绝不是偶发的和个别的。 值得格外注意的是，针对地主富农的这种打击越多，中共基层党政部门看到的来自地主富农分子的敌意、反抗和报复也就越加明显和激烈。这种情况反过来也就越发 促使中共多数地方领导人高度警觉，绝不相信地富丧失了财产和地位，就应该给其与一般人一样的待遇，而中共地方实际工作部门的意见，又足以改变中共中央的看 法。

　　1951年5月10日，中共中央鉴于各地土改走向尾声，开始从恢复经济和统战关系的角度，考虑对多数已经接受了现状的地主适当采取 羁糜政策，并据此发出了一个关于土改后安置地主就业的指示。要求各级干部在土改完成的地区，劝说农民"主动地向那些表示服从的地主和缓一下"，"以便争取 多数地主参加劳动，耕种自己所分得的土地，维持自己的生活。对于地主阶级中的知识分子或有其他技能，可能从事教书或其他职业者，应允许他们从事其他职业， 或分配教书工作给他们。对于确实没有农业劳动力，而能作生意者，可以允许他们作生意。"要让他们了解："他们的底财，可以允许他们挖出来，投资生产，不再 没收。他们以后生产所得，不论多少，均不再没收。"只对那些有劳动力，能从事农业劳动，又无其他职业者，应强制他们劳动，不允许他们游手好闲以讨饭为生。 对于那些继续顽抗的地主，除应继续斗争外，"亦可把他们编成劳役队强迫他们劳动"。

　　这一指示没有得到各地的拥护和响应。相反，各中央局对向地主表示缓和的作法多不赞成。他们深信遭到土改严酷打击的地主分子，绝不会 安分守己，多半都会怀恨破坏或反攻倒算。华东局因此提出了一个与上面的指示完全不同的管制和改造地主的文件，称："在土地分配已经完成的地区，为了防止地 主反攻复辟、窃取农民的斗争果实，继续压迫农民，必须对他们提高警惕，并严格地进行管制，不能稍有麻痹懈怠。""在对地主管制期间，应强迫他们参加劳动和 经常对他们进行政治教育同时并进。乡人民政府和乡农民协会，应近期按期召集地主训话，检查其劳动改造及遵行管制规定的情形。"只有"对确实长期安分守法积 极劳动并较一般地主表现为好的个别地主"，可以"酌情缩短其管制期限"。对于华东局的这一文件，中共中央亦不能不表示赞同，并转发各地参考执行。

　　来自地方上的这种报告看多了，毛泽东、刘少奇等人的看法也很快就变过来了。只过了将近一年半，中共中央就根本改变了在这一问题上的 看法，并且开始修正原定地主劳动满5年、富农不剥削满3年就可以给他们公民权的决定，强调对地富恢复公民权利问题，"根据各地区不少地富的破坏活动及抗拒 政府法令的行为看，目前似不宜做统一的明文规定"，只可个别试点。毛泽东后来甚至根本反对轻易给地富分子摘帽子。他说："过去规定摘地主帽子一般是三五 年，现在看来，恐怕要到三十到五十年。"刘少奇解释说：因为苏联过去是把地富都驱逐了，而我们没有这样做，还和地富在一起，因此如果界线划不清会很危险。

　　中共土改对地主富农简单一刀切的做法，并不纯粹来自于意识形态，它很大程度上与中共的现实考虑相关联。中共早期的农村政策，只把矛 头对准土豪劣绅和大地主阶级，并不主张反对小地主。大家都清楚，小地主生活亦苦，也受帝国主义、军阀和大地主的压迫，故相信从统一战线的角度应当联合小地 主，共同反对土豪劣绅和大地主阶级。1927年中共明确提出土地革命的方针，宣布"无代价地没收地主租与农民的土地"时，仍公开承诺"属于小地主的土地不 没收"。1927年大革命失败之后，对小地主的这一政策改变了，因为要发动农民跟随共产党，必须给农民好处，而中国南方许多地方没有大地主，只能拿小地主 开刀，因此就再不提区别大小地主的事情了。

　　抗战期间，中共因为放弃了土地革命的政策，改行减租减息和三三制，有了许多开明士绅的统战对象。因此，当1946年中共中央不能不 再行土改之初，就又一次突出强调其区别的问题。《五四指示》中就明确提出了"对待中小地主的态度应与对待大地主、豪绅、恶霸的态度有所区别"的具体办法。 1947年2月1日，毛泽东也重申了这一政策，要求"对于一般的富农和中小地主，在土地改革中和土地改革后，应有适当的出于群众愿意的照顾"。但这一政策 因无法满足众多无地少地农民的愿望和需要，在1947年4月之后实际上被负责土改工作的刘少奇放弃了。从1947年10月颁布的《中国土地法大纲》，到 1950年6月颁布的《中华人民共和国土地改革法》，都不再有区别大小地主的提法和政策。
 

china culture Comments(3) 2011年5月13日 03:26

（轉載）美國大學生讀什麼書瞭解中國

原始文章來自http://www.chinaelections.org/newsinfo.asp?newsid=204800

 

 最近一位在美国教中国政治的教授给笔者所在的listserv发信询问大家在自己教授的与中国有关的课程上都使用什么书。有不少教授回复。之后，这位教授整理出来一个名单并发到listserv供大家参考。

    笔者不无遗憾的发现被中国叫好的几本书都不在名单上，其中包括库恩的《江泽民传》、纳斯比特的《中国大趋势》和雅克的《中国将征服世界》。

    笔者还发现这些书基本上都是纪实或文学作品，不是学术专著。

    笔者不认为这个名单没有偏差，但是通过了解教授们提出的书目，我们也许可以更好地了解美国学者的所好及美国学生认识中国的资料。

    也许，这个名单也可以给那些打造中国软实力的政府机构和官员提供一个可以参考的“联络图”。

去年用书书目：（15）
　　帕拉维·艾雅尔 《烟雾与镜子:中国经历》
　　Aiyar, Pallavi, Smoke and Mirrors

　　凯瑞·布朗 《疲于奔命的巨人：21世纪中国》
　　Brown, Kerry, Struggling Giant, China in the 21st Century

　　罗德·吉福特《中国行》
　　Gifford, Rob, China Road

　　彼得·海斯勒 (何伟) 《寻路中国》
　　Hessler, Peter, Country Driving

　　彼得·海斯勒 (何伟) 《甲骨：游历于中国的历史与现实之间》
　　Hessler, Peter, Oracle Bones:  A Journey Between China's Past and Present

　　邓肯·海维特《先富起来：生活在开放中的中国》
　　Hewitt, Duncan, Getting Rich First

　　哈金《疯狂》
　　Jin, Ha, The Crazed

　　伊恩·约翰逊《野草：当代中国三个变革的故事》
　　Johnson, Ian, Wild Grass:  Three Stories of Change in Modern China

　　詹姆斯·金奇《中国震憾世界-饥饿之国的崛起》
　　Kynge, James, China Shakes the World:  The Rise of a Hungry Nation

　　廖亦武 《中国底层社会实录》
　　Liao, Yiwu, The Corpse Walker; Real-Life Stories, China from the Bottom Up

　　马建 《北京植物人》
　　Ma, Jian, Beijing Coma

　　迈克尔·梅尔《老北京的最后岁月》
　　Meyer, Michael, The Last Days of Old Beijing

　　潘公凯 《走出毛的阴影：追寻新中国的灵魂》
　　Pan, Philip, Out of Mao's Shadow: The Struggle for the Soul of a New China

　　潘文 《中国教训：五位同学及新中国的故事》
　　Pomfret, John, Chinese Lessons: Five Classmates and the Story of the New China

　　张丽佳 《社会主义好》
　　Zhang, Lijia, Socialism is Great!

建议用书书目：（24）
　　奥利佛·欧古斯特 《红楼深深》
　　August, Oliver, Inside the Red Mansion

　　张彤禾 《工厂女工》
　　Chang, Leslie, Factory Girls

　　陈桂棣、吴春桃 《中国农民报告》
　　Chen Guidi, Wu Chuntao and Zhu Hong, Will the Boiat Sink the Water?  The Life of China's Peasants

　　林瑞秋 《外国宝贝在北京》
　　Dewoskin, Rachel, Foreign Babes in Beijing

　　詹姆斯·法罗斯《从明天广场发出的明信片》
　　Fallows, James, Postcards from Tomorrow Square

　　亚历山大·哈尼《探寻中国制造的价格优势》
　　Harney, The China Price: The True Cost of Chinese Competitive Advantage

　　彼得·海斯勒 (何伟)《消失中的江城：一位西方作家在長江古城探索中国》
　　Hessler, River Town

　　康正果 《出中国记：我的反动自述》
　　Kang, Zhengguo, Confessions:  An Innocent Life in Communist China

　　马克·莱纳德 《中国怎么想》
　　Leonard, Mark, What Does China Think?

　　李存信 《毛的最后一个舞者》
　　Li, Cunxin, Mao's Last Dancer

　　李翊云 《流浪汉》
　　Li, Yiyun, The Vagrants

　　亚伯拉罕·勒斯特加滕《华夏天路》
　　Lustgarten, Abraham, China's Great Train

　　丹尼尔·露西 《拉里的肾》
　　Rose, Daniel Asa, Larry's Kidney

　　詹姆斯·麦格雷戈 《十亿消费者》
　　McGregor, Jim, One billion Customers

　　梅文诗《红色狂想曲：西方古典音乐如何改变中国》
　　Melvin, Sheila, Rhapsody in Red

　　圣扎迦利·麦克西克 《中国深度游》
　　Mexico, Zachary, China Underground

　　裘小龙 《红尘岁月：大上海的故事》
　　Qiu, Xiaolong, Years of Red Dust, Stories of Shanghai

　　桑晔、白杰明 《真实的中国：共和国的人民》
　　Sang, Ye and Geremie Barme, China Candid: The People in the People's Republic

　　华衷《当十亿中国人一起跳起来》
　　Watts, Jonathan, When a Billion Chinese Jump (about environmental issues)

　　欣然 《见证中国: 沉默一代的声音》
　　Xinran, China Witness

　　欣然 《中国妇女》
　　Xinran, The Women of China

　　余华 《兄弟》
　　Yu, Hua, Brothers

　　査建英 《弄潮儿》
　　Zha Jianying, Tide Players

　　ZZ 《中国，高！》
　　ZZ, China High

china culture china，culture Comments(11) 2011年4月18日 18:20

LINUX下如何代替fflush(stdin)

在windows下為了清空鍵盤區緩存，往往使用以下命令。

fflush(stdin)

可是這個命令在linux下是通不過的，為了使用代碼更具有通用性，我們可以將其換為

fgectc(stdin)

fgectchc的作用是返回stream流的下一個字符，返回類型為unsigned char(被轉換為int類型)，如果到達文件末尾或發生錯誤，

則返回EOF。

具體可以參攷這扁文章http://is.gd/FUcpxb

最後呼籲釋放艾未未

C／C＋＋ c Comments(39) 2011年4月09日 02:26