2011-9-7 5:06:00 Fundamental algorithms
Office hour: Mon 4:00-5:00
Tue 3:00-4:00
Wed
Thu 3:00-4:00
homework
once every week
write on your own
lecture notes
math use a lot during this class
homework 40% mid-term 20% final 40%
lecture 1—Outline of algorithms
I. what is algorithms ?
II. what are problems ?
III. how to resolve problems ? model of complication
IV. how to measure algorithms?
V. How to design a good algorithms?
VI. How to accesscomplaxible
VII. Asymptotics
I.
1.
Problem can be solved.
Small problems is the aim of this course.
Very well defined, certain , clear that is the small mean.
II.
Input-output problems
Sorting problems (increasing lines)
Primality problems (yes or no)
质数
Preprocessing problems
Input
Ranking problem
III. how do we solve these problems ?
Model of competition:
Data type
Primitive operations
Composition rules
Ex. Compare tree
*Algorithms = A program that solve a particular problem IV. How to measure algorithms? Which solution is better? Compare
Circuit model
A.number
https://www.doczj.com/doc/b83924816.html,pare
C.circuit
ex. computer tape
VI.
Time / space / other kinds of resource
We usually take one to discuses.
VI.
What is the cost for each primate operation ?
Time!!
Space!
As simple as possible
VII.
Asymptotics
X: input
A: program
Ta: x->N={0,1,2,….}
T is a function. T(a) is the result of this function.
Max time/ average time/
Worst case/ average case/
Size of the input should be considered.
Algorithms method
V. how to design a good method?
Sorting problem
Inherent complexity of sorting
Hasse diagram
At least 3
Information theoretic bond
Know about the number of leaves
Height of tree.
f: R->L partial function
for x(i)>=x(0), f(x)>=g(x) that’s what partial function