麻省理工学院：《算法导论》（英文版） Lecture Prof. Charles E. Leiserson

Introduction to algorithms 6.046J/18.401J/SMA5503 Lecture l Prof. charles e. leiserson

Introduction to Algorithms 6.046J/18.401J/SMA5503 Lecture 1 Prof. Charles E. Leiserson

Welcome to introduction to Algorithms, Fall 2001 Handouts 1. Course Information 2. Calendar 3. Registration (MIT students only) 4. References 5. Objectives and Outcomes 6. Diagnostic survey Day 1 Introduction to Algorithms L12

Day 1 Introduction to Algorithms L1.2 Welcome to Introduction to Algorithms, Fall 2001 Handouts 1. Course Information 2. Calendar 3. Registration (MIT students only) 4. References 5. Objectives and Outcomes 6. Diagnostic Survey

Course information 1. Staff 8. Website 2. Distance learning 9. Extra help 3. Prerequisites 10. Registration MIT only) 4. Lectures 11. Problem sets 5. Recitations 12. Describing algorithms 6. Handouts 13.G1 rading policy 7. Textbook(CLRS) 14. Collaboration policy Course information handout Day 1 Introduction to Algorithms 1.3

Day 1 Introduction to Algorithms L1.3 Course information 1. Staff 2. Distance learning 3. Prerequisites 4. Lectures 5. Recitations 6. Handouts 7. Textbook (CLRS) 8. Website 9. Extra help 10.Registration (MIT only) 11.Problem sets 12.Describing algorithms 13.Grading policy 14.Collaboration policy ¾ Course information handout

Analysis of algorithms The theoretical study of computer-program performance and resource usage What's more important than performance? modularity o user-friendliness correctness programmer time maintainability simplicity functionality extensibility robustness reliability Day 1 Introduction to Algorithms

Day 1 Introduction to Algorithms L1.4 Analysis of algorithms The theoretical study of computer-program performance and resource usage. What’s more important than performance? • modularity • correctness • maintainability • functionality • robustness • user-friendliness • programmer time • simplicity • extensibility • reliability

Why study algorithms and performance? Algorithms help us to understand scalability Performance often draws the line between what is feasible and what is impossible Algorithmic mathematics provides a language for talking about program behavior The lessons of program performance generalize to other computing resources Speed is fun! Day 1 Introduction to Algorithms 1.5

Day 1 Introduction to Algorithms L1.5 Why study algorithms and performance? • Algorithms help us to understand scalability. • Performance often draws the line between what is feasible and what is impossible. • Algorithmic mathematics provides a language for talking about program behavior. • The lessons of program performance generalize to other computing resources. • Speed is fun!

The problem of sorting Input: sequence(a1, a2,.,an,of numbers Output: permutation (al, a2,..., an such that a1≤a2≤…≤an Example: put:824936 Output: 23 4689 Day 1 Introduction to Algorithms L16

Day 1 Introduction to Algorithms L1.6 The problem of sorting Input: sequence 〈a1, a2, …, an〉 of numbers. Example: Input: 8 2 4 9 3 6 Output: 2 3 4 6 8 9 Output: permutation 〈a'1, a'2, …, a'n〉 such that a'1 ≤ a'2 ≤ … ≤ a'n

Insertion sort INSERTION-SORT(A, n) D Al.n forj←2ton do key←Aj pseudocode while i>0 and a[i> key doA[i+1]←A[d Ai+1=key sorted ey Day 1 Introduction to Algorithms 17

Day 1 Introduction to Algorithms L1.7 Insertion sort INSERTION-SORT (A, n) ⊳ A[1 . . n] for j ← 2 to n do key ← A[ j] i ← j – 1 while i > 0 and A[i] > key do A[i+1] ← A[i] i ← i – 1 A[i+1] = key “pseudocode” i j key sorted A: 1 n

Example of insertion sort 824936 Day 1 Introduction to Algorithms

Day 1 Introduction to Algorithms L1.8 Example of insertion sort 824936

Example of insertion sort 824936 Day 1 Introduction to Algorithms 1.9

Day 1 Introduction to Algorithms L1.9 Example of insertion sort 824936

Example of insertion sort 824 36 284 99 36 Day 1 Introduction to Algorithms L1.10

Day 1 Introduction to Algorithms L1.10 Example of insertion sort 824936 284936