advertisement

advertisement

Information about Introduction to algorithms

advertisement

Algorithms Introduction Proof By Induction Asymptotic notation

Pre Computer Era: • In the pre computer era various models of computation were proposed. The models worked on a predefined set of operations. The primary focus in this era was on “What can be computed and what cannot be computed?” This field of study was called Computability Theory. Sandeep Kumar Poonia

Post Computer Era: • With ultimate computability in terms of Turing Machines, the primary focus in the post computer era was Complexity Theory. People were more interested to find out “How well can it be computed?” Sandeep Kumar Poonia

Sandeep Kumar Poonia

Sandeep Kumar Poonia

Sandeep Kumar Poonia

As a corollary to the above mentioned result we can easily see that a number n must be halved floor(log2n) + 1 times to reach 0. Sandeep Kumar Poonia

Algorithms •An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. •An algorithm is thus a sequence of computational steps that transform the input into the output. Sandeep Kumar Poonia

Algorithms Sandeep Kumar Poonia

Algorithms Sandeep Kumar Poonia

Properties of Algorithms Sandeep Kumar Poonia

Steps to develop an algorithm Sandeep Kumar Poonia

Algorithms as a technology •Suppose computers were infinitely fast and •computer memory was free. Would you have any reason to study algorithms?......YES(See an example) let us assume a faster computer (computer A) running insertion sort against a slower computer (computer B) running merge sort. They each must sort an array of one million numbers. Suppose that computer A executes one billion instructions per second and computer B executes only ten million instructions per second, so that computer A is 100 times faster than computer B in raw computing power. insertion sort, takes time roughly equal to c1n2 to sort n items, merge sort, takes time roughly equal to c2n lg n Sandeep Kumar Poonia

Algorithms as a technology To sort one million numbers, • Computer A takes • Computer B takes By using an algorithm whose running time grows more slowly, even with a poor compiler, computer B runs 20 times faster than computer A Sandeep Kumar Poonia

Review: Induction • Suppose S(k) is true for fixed constant k o Often k = 0 S(n) S(n+1) for all n >= k • Then S(n) is true for all n >= k Sandeep Kumar Poonia

Proof By Induction • Claim:S(n) is true for all n >= k • Basis: Show formula is true when n = k • Inductive hypothesis: Assume formula is true for an arbitrary n • Step: Show that formula is then true for n+1 Sandeep Kumar Poonia

Induction Example: Gaussian Closed Form • Prove 1 + 2 + 3 + … + n = n(n+1) / 2 Basis: o If n = 0, then 0 = 0(0+1) / 2 Inductive hypothesis: o Assume 1 + 2 + 3 + … + n = n(n+1) / 2 Step (show true for n+1): 1 + 2 + … + n + n+1 = (1 + 2 + …+ n) + (n+1) = n(n+1)/2 + n+1 = [n(n+1) + 2(n+1)]/2 = (n+1)(n+2)/2 = (n+1)(n+1 + 1) / 2 Sandeep Kumar Poonia

Induction Example: Geometric Closed Form • Prove a0 + a1 + … + an = (an+1 - 1)/(a - 1) for all a 1 Basis: show that a0 = (a0+1 - 1)/(a - 1) a0 = 1 = (a1 - 1)/(a - 1) Inductive hypothesis: o Assume a0 + a1 + … + an = (an+1 - 1)/(a - 1) Step (show true for n+1): a0 + a1 + … + an+1 = a0 + a1 + … + an + an+1 = (an+1 - 1)/(a - 1) + an+1 = (an+1+1 - 1)/(a - 1) Sandeep Kumar Poonia

Induction • • We’ve been using weak induction Strong induction also holds Basis: show S(0) Hypothesis: assume S(k) holds for arbitrary k <= n Step: Show S(n+1) follows • Another variation: Basis: show S(0), S(1) Hypothesis: assume S(n) and S(n+1) are true Step: show S(n+2) follows Sandeep Kumar Poonia

Asymptotic Performance • Here, we care most about asymptotic performance How does the algorithm behave as the problem size gets very large? o Running time o Memory/storage requirements o Bandwidth/power requirements/logic gates/etc. Sandeep Kumar Poonia

Asymptotic Notation • By now you should have an intuitive feel for asymptotic (big-O) notation: What does O(n) running time mean? O(n2)? O(n lg n)? How does asymptotic running time relate to asymptotic memory usage? • Our first task is to define this notation more formally and completely Sandeep Kumar Poonia

Analysis of Algorithms • Analysis is performed with respect to a • computational model We will usually use a generic uniprocessor random-access machine (RAM) All memory equally expensive to access No concurrent operations All reasonable instructions take unit time o Except, of course, function calls Constant word size o Unless we are explicitly manipulating bits Sandeep Kumar Poonia

Input Size • Time and space complexity This is generally a function of the input size o E.g., sorting, multiplication How we characterize input size depends: o Sorting: number of input items o Multiplication: total number of bits o Graph algorithms: number of nodes & edges Etc Sandeep Kumar Poonia

Running Time • Number of primitive steps that are executed Except for time of executing a function call most statements roughly require the same amount of time oy=m*x+b o c = 5 / 9 * (t - 32 ) o z = f(x) + g(y) • We can be more exact if need be Sandeep Kumar Poonia

Analysis • Worst case Provides an upper bound on running time An absolute guarantee • Average case Provides the expected running time Very useful, but treat with care: what is “average”? o Random (equally likely) inputs o Real-life inputs Sandeep Kumar Poonia

An Example: Insertion Sort InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 30 10 40 20 1 2 3 4 i = j = key = A[j] = A[j+1] = InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 30 10 40 20 1 2 3 4 i=2 j=1 A[j] = 30 key = 10 A[j+1] = 10 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 30 30 40 20 1 2 3 4 i=2 j=1 A[j] = 30 key = 10 A[j+1] = 30 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 30 30 40 20 1 2 3 4 i=2 j=1 A[j] = 30 key = 10 A[j+1] = 30 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 30 30 40 20 1 2 3 4 i=2 j=0 A[j] = key = 10 A[j+1] = 30 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 30 30 40 20 1 2 3 4 i=2 j=0 A[j] = key = 10 A[j+1] = 30 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 20 1 2 3 4 i=2 j=0 A[j] = key = 10 A[j+1] = 10 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 20 1 2 3 4 i=3 j=0 A[j] = key = 10 A[j+1] = 10 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 20 1 2 3 4 i=3 j=0 A[j] = key = 40 A[j+1] = 10 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 20 1 2 3 4 i=3 j=0 A[j] = key = 40 A[j+1] = 10 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 20 1 2 3 4 i=3 j=2 A[j] = 30 key = 40 A[j+1] = 40 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 20 1 2 3 4 i=3 j=2 A[j] = 30 key = 40 A[j+1] = 40 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 20 1 2 3 4 i=3 j=2 A[j] = 30 key = 40 A[j+1] = 40 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 20 1 2 3 4 i=4 j=2 A[j] = 30 key = 40 A[j+1] = 40 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 20 1 2 3 4 i=4 j=2 A[j] = 30 key = 20 A[j+1] = 40 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 20 1 2 3 4 i=4 j=2 A[j] = 30 key = 20 A[j+1] = 40 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 20 1 2 3 4 i=4 j=3 A[j] = 40 key = 20 A[j+1] = 20 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 20 1 2 3 4 i=4 j=3 A[j] = 40 key = 20 A[j+1] = 20 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 40 1 2 3 4 i=4 j=3 A[j] = 40 key = 20 A[j+1] = 40 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 40 1 2 3 4 i=4 j=3 A[j] = 40 key = 20 A[j+1] = 40 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 40 1 2 3 4 i=4 j=3 A[j] = 40 key = 20 A[j+1] = 40 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 40 1 2 3 4 i=4 j=2 A[j] = 30 key = 20 A[j+1] = 40 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 40 40 1 2 3 4 i=4 j=2 A[j] = 30 key = 20 A[j+1] = 40 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 30 40 1 2 3 4 i=4 j=2 A[j] = 30 key = 20 A[j+1] = 30 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 30 40 1 2 3 4 i=4 j=2 A[j] = 30 key = 20 A[j+1] = 30 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 30 40 1 2 3 4 i=4 j=1 A[j] = 10 key = 20 A[j+1] = 30 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 30 30 40 1 2 3 4 i=4 j=1 A[j] = 10 key = 20 A[j+1] = 30 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 20 30 40 1 2 3 4 i=4 j=1 A[j] = 10 key = 20 A[j+1] = 20 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

An Example: Insertion Sort 10 20 30 40 1 2 3 4 i=4 j=1 A[j] = 10 key = 20 A[j+1] = 20 InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Done! Sandeep Kumar Poonia

Insertion Sort What is the precondition InsertionSort(A, n) { for this loop? for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } } Sandeep Kumar Poonia

Insertion Sort InsertionSort(A, n) { for i = 2 to n { key = A[i] j = i - 1; while (j > 0) and (A[j] > key) { A[j+1] = A[j] j = j - 1 } A[j+1] = key } How many times will } this loop execute? Sandeep Kumar Poonia

Insertion Sort Statement Effort InsertionSort(A, n) { for i = 2 to n { c1n key = A[i] c2(n-1) j = i - 1; c3(n-1) while (j > 0) and (A[j] > key) { c4T A[j+1] = A[j] c5(T-(n-1)) j = j - 1 c6(T-(n-1)) } 0 A[j+1] = key c7(n-1) } 0 } T = t2 + t3 + … + tn where ti is number of while expression evaluations for the ith for loop iteration Sandeep Kumar Poonia

Analyzing Insertion Sort • • T(n) = c1n + c2(n-1) + c3(n-1) + c4T + c5(T - (n-1)) + c6(T - (n-1)) + c7(n-1) = c8T + c9n + c10 What can T be? Best case -- inner loop body never executed o ti = 1 T(n) is a linear function Worst case -- inner loop body executed for all previous elements o ti = i T(n) is a quadratic function Sandeep Kumar Poonia

Analysis • Simplifications Ignore actual and abstract statement costs Order of growth is the interesting measure: o Highest-order term is what counts Sandeep Kumar Poonia Remember, we are doing asymptotic analysis As the input size grows larger it is the high order term that dominates

Upper Bound Notation • We say InsertionSort’s run time is O(n2) Properly we should say run time is in O(n2) Read O as “Big-O” (you’ll also hear it as “order”) • In general a function f(n) is O(g(n)) if there exist positive constants c and n0 such that f(n) c g(n) for all n n0 • Formally O(g(n)) = { f(n): positive constants c and n0 such that f(n) c g(n) n n0 Sandeep Kumar Poonia

Lower Bound Notation • We say InsertionSort’s run time is (n) • In general a function f(n) is (g(n)) if positive constants c and n0 such that 0 cg(n) f(n) n n0 • Proof: Suppose run time is an + b o Assume a and b are positive (what if b is negative?) an an + b Sandeep Kumar Poonia

Asymptotic Tight Bound • A function f(n) is (g(n)) if positive constants c1, c2, and n0 such that c1 g(n) f(n) c2 g(n) n n0 • Theorem f(n) is (g(n)) iff f(n) is both O(g(n)) and (g(n)) Sandeep Kumar Poonia

Practical Complexity 250 f(n) = n f(n) = log(n) f(n) = n log(n) f(n) = n^2 f(n) = n^3 f(n) = 2^n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Sandeep Kumar Poonia

Practical Complexity 500 f(n) = n f(n) = log(n) f(n) = n log(n) f(n) = n^2 f(n) = n^3 f(n) = 2^n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Sandeep Kumar Poonia

Practical Complexity 1000 f(n) = n f(n) = log(n) f(n) = n log(n) f(n) = n^2 f(n) = n^3 f(n) = 2^n 0 1 Sandeep Kumar Poonia 3 5 7 9 11 13 15 17 19

Practical Complexity 5000 4000 f(n) = n f(n) = log(n) 3000 f(n) = n log(n) f(n) = n^2 2000 f(n) = n^3 f(n) = 2^n 1000 0 1 Sandeep Kumar Poonia 3 5 7 9 11 13 15 17 19

Practical Complexity 10000000 1000000 100000 10000 1000 100 10 1 1 Sandeep Kumar Poonia 4 16 64 256 1024 4096 16384 65536

Other Asymptotic Notations • A function f(n) is o(g(n)) if positive • • constants c and n0 such that f(n) < c g(n) n n0 A function f(n) is (g(n)) if positive constants c and n0 such that c g(n) < f(n) n n0 Intuitively, o() is like < O() is like Sandeep Kumar Poonia () is like > () is like () is like =

Thomas H. - Introduction to Algorithms jetzt kaufen. ISBN: 9780262531962, Fremdsprachige Bücher - Algebra

Read more

Thomas H. - Introduction to Algorithms jetzt kaufen. ISBN: 9780262533058, Fremdsprachige Bücher - Programmieren

Read more

Buy Introduction to Algorithms, 3rd Edition (MIT Press) on Amazon.com FREE SHIPPING on qualified orders

Read more

Some books on algorithms are rigorous but incomplete; others cover masses of material but lack rigor. Introduction to Algorithms uniquely combines rigor ...

Read more

Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein Introduction to Algorithms Third Edition The MIT Press Cambridge, Massachusetts ...

Read more

This course provides an introduction to mathematical modeling of computational problems. It covers the common algorithms, algorithmic paradigms, and data ...

Read more

Thomas H. Cormen Charles E. Leiserson Ronald L. Rivest Clifford Stein Introduction to Algorithms Third Edition The MIT Press Cambridge, Massachusetts ...

Read more

Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. It is used as the textbook for ...

Read more

The first edition won the award for Best 1990 Professional and Scholarly Book in Computer Science and Data Processing by the Association of American ...

Read more

When I first encountered "Introduction to algorithms" at 15, the mere idea of reading an "Introduction" of 1202 pages, seemed very exhausting to me. At ...

Read more

## Add a comment