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