MIT6.006农民工学算法导论

文章目录

• GOAL of algorithm
• Algorithms and computation
  • Model of computation
• 学习顺序

GOAL of algorithm

goal：—-communication

1. solve compucating problems
2. prove correctness
3. argue efficiency

Algorithms and computation

problems：

1. discrete mathematics 离散数学 Inputs—-outputs …. ….
2. general problems arbitrary inputs

Exp: for birthday problems -maintain record interview every student

procedure - algorithms

1. Correct:induction -归纳法 -就职 引起 -base case 0 1… K=0 assume
2. Effeciency -asymptotic analysis渐进分析 O（）———- upper bound Omega（）——lower bounds Theta()——-both

Model of computation

Word - RAM :world - chunk- 64 bits one read from mem store that address in CPU 2-32 —-4 GB——Limitation 64 bits —-20 exabytes

学习顺序

Data structures and sorting—-> shortest paths, algorithms, and graphs——> dynamic programming