1 Syllabus
Please refer to the instructor's document.
2 Basic Theory
2.1 Approximation algorithm
Approximation algorithm: You can guarantee by this solution with a certain
time, but then you cannot guarantee how good the solution is. Then you try
to de sign algorithm that in certain time, the solution is as best as possible.
2.2 Simplex Method
In some cases, you still want the optimal solution, but you know that there
is no algorithm currently to find an optimal solution always, sometimes,
eg. Simplex Method, is a method solve linear system , so to solve linear
systems, the simplex method is developed in 1940, scientist from England.
Simplex Method is proven in the worst case, take exp onential time to solve
the system, however, in practice this method is actually very good. People
still use simplex system, it is very fast in practice. Average is very tricky,
if
we talk about average, we have to talk about for what kind of input. Given
a group of input , for each of it, it has spend a certain time, calculate the
probability distribution of the input , if we have 1
2.3 Sooth complexity
Smooth complexity, in the worst case, it is very bad, since computer has
errors, for the input, we use computer to write a program, most time it
does not solve the exactly original question. It solve some perturb question.
Sooth complexity, for some questions we know that in the worst case, it
could be very bad, however, for any question, if I proturb this question a
little bit, then with half ability, it could solve very quickly. And also the
solution of the proturbed question is similar to the original question.
3 Basic Knowledge
3.1 Set
Set: A group of Elements
Subset: A 
B
Proper Subset: A 
B
Power Set: 2A
Venn Diagram:
3.2 Function
For every element in A, we map to only one element in B.
3.3 Relation
Relation is some special function that is map to 0 or 1.
R (...) → 0 or1
≥ This is a relation.
for any 2 elements: ≥ (x, y) → 1 or 0
3.4 Graph
Defination 1: a set of vertices and eges to connect them.
Defination 2: use a relation to define.
Path: a sequence of vertices 
3.5 String
String is a sequence of characters.
∑:alphabet
eg. ∑:a,b,c,d... x,y,z
Ope ration of String :
Given 2 strings W and V:
(1) concatenate them: WV
(2) repeat this string, include 0 times: 
(3) repeat this string at least 1 time : 
3.6 Boolean Logic
4 Proof techniques
A statement could be true or false, if a statement is true, we call it:
Lemma: This is used to proof Theorem.
Theorem: Significant proof to be true.
Corollary: Result proof from theorem.
4.1 Proof by contradiction
Example: Prove 
is not a rational number.
We can assume is rational, thus
p and q are coprime, so gcd(p,q)=1. From (1) we get:
thus, 
thus, 2 l gcd(p, q), this contradicts gcd(p,q)=1. Therefore the as sumption is
false , so is not rational.
4.2 Proof by construction
National number:
is countable.
There are 2 methods to define a set A countable:
(1) It is finite.
(2) A function mapping to a national number: f : A → N
eg. Given a set 
It is countable because: f : x → 
Example: Is rational numbers countable ? A rational number can be de-
fined as 
, then we can construct a table:
View this table diagonally, we can find a mapping:
Therefore, we can proof the rational numbers are
countable.
Example: Is real number countable?
As the countable numbers have a exist function:
: A → N, to proof real
numbers are not countable, we should proof this function does not exists.
We can proof this by contradiction. So there are 2 steps : First we construct
a function, and then proof there is a contradiction.
Assume there is a function f : A → N A∈ (0, 1), and proof there exists a
number cannot map by this function.
This is to proof: 
, f(x) is not defined.
We can construct a table:
|
N |
real numbers |
 |
We can find x ∈ (0, 1) that is not in the table. We can
construct a
number which is different with each digit in each row. For example, for
the 1st digit in 1st row, the number is 1, so the 1st digit of the number se
construct should be any numbers other than 1, so this number should not
be find in the 1st row. For the 2nd digit in 2nd row, the number is 1, so 2nd
digit of the number should not be 1, and so on. We can construct a number
which cannot be put in any row in this table. As there is a number does
not map by this function, so there is a controdiction, thus the assumption
is false. So the real number cannot be countable.
