DOC PREVIEW
IUPUI CS 580 - Introduction to Algorithm design and analysis

This preview shows page 1-2-21-22 out of 22 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 22 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Introduction to Algorithm design and analysisEfficiency comparison of two algorithmsAlgorithm Design and AnalysisInsertion Sort Algorithm (cont.)Correctness of Insertion Sort AlgorithmAnalysis of Insertion SortAnalysis of Insertion Sort (cont.)Merge Sort—divide-and-conquerMerge Sort –merge functionMERGE-SORT(A,p,r)Analysis of Divide-and-ConquerAnalysis of MERGE-SORTCompute T(n) by Recursive TreeRecursion tree of T(n)=2T(n/2)+cnOrder of growthSlide 16Prove f(n)=an2+bn+c=(n2)o-notationNotes on o-notation-notationTechniques for Algorithm Design and AnalysisNP-complete problem1Introduction to Algorithm design and analysisExample: sorting problem.Input: a sequence of n number a1, a2, …,anOutput: a permutation (reordering) a1', a2', …,an' such that a1' a2'  …  an '.Different sorting algorithms: Insertion sort and Mergesort.2Efficiency comparison of two algorithms•Suppose n=106 numbers: –Insertion sort: c1n2–Merge sort: c2n (lg n)–Best programmer (c1=2), machine language, one billion/second computer A.–Bad programmer (c2=50), high-language, ten million/second computer B.–2 (106)2 instructions/109 instructions per second = 2000 seconds.–50 (106 lg 106) instructions/107 instructions per second  100 seconds.–Thus, merge sort on B is 20 times faster than insertion sort on A!–If sorting ten million numbers, 2.3 days VS. 20 minutes. •Conclusions:–Algorithms for solving the same problem can differ dramatically in their efficiency.–much more significant than the differences due to hardware and software.3Algorithm Design and Analysis•Design an algorithm –Prove the algorithm is correct.•Loop invariant.•Recursive function.•Formal (mathematical) proof.•Analyze the algorithm–Time•Worse case, best case, average case. •For some algorithms, worst case occurs often, average case is often roughly as bad as the worst case. So generally, worse case running time.–Space•Sequential and parallel algorithms–Random-Access-Model (RAM)–Parallel multi-processor access model: PRAM4Insertion Sort Algorithm (cont.)INSERTION-SORT(A)1. for j = 2 to length[A]2. do key  A[j]3. //insert A[j] to sorted sequence A[1..j-1]4. i  j-15. while i >0 and A[i]>key 6. do A[i+1]  A[i] //move A[i] one position right7. i  i-18. A[i+1]  key5Correctness of Insertion Sort Algorithm•Loop invariant–At the start of each iteration of the for loop, the subarray A[1..j-1] contains original A[1..j-1] but in sorted order.•Proof:–Initialization : j=2, A[1..j-1]=A[1..1]=A[1], sorted.–Maintenance: each iteration maintains loop invariant.–Termination: j=n+1, so A[1..j-1]=A[1..n] in sorted order.6Analysis of Insertion Sort INSERTION-SORT(A) cost times 1. for j = 2 to length[A] c1n2. do key  A[j] c2n-13. //insert A[j] to sorted sequence A[1..j-1] 0 n-14. i  j-1 c4n-15. while i >0 and A[i]>key c5j=2n tj6. do A[i+1]  A[i] c6j=2n(tj –1)7. i  i-1 c7j=2n(tj –1)8. A[i+1]  key c8n –1(tj is the number of times the while loop test in line 5 is executed for that value of j)The total time cost T(n) = sum of cost  times in each line =c1n + c2(n-1) + c4(n-1) + c5j=2n tj+ c6j=2n (tj-1)+ c7j=2n (tj-1)+ c8(n-1)7Analysis of Insertion Sort (cont.)•Best case cost: already ordered numbers–tj=1, and line 6 and 7 will be executed 0 times–T(n) = c1n + c2(n-1) + c4(n-1) + c5(n-1) + c8(n-1) =(c1 + c2 + c4 + c5 + c8)n – (c2 + c4 + c5 + c8) = cn + c‘ •Worst case cost: reverse ordered numbers–tj=j, –so j=2n tj = j=2n j =n(n+1)/2-1, and j=2n(tj –1) = j=2n(j –1) = n(n-1)/2, and –T(n) = c1n + c2(n-1) + c4(n-1) + c5(n(n+1)/2 -1) + + c6(n(n-1)/2 -1) + c7(n(n-1)/2)+ c8(n-1) =((c5 + c6 + c7)/2)n2 +(c1 + c2 + c4 +c5/2-c6/2-c7/2+c8)n-(c2 + c4 + c5 + c8) =an2+bn+c•Average case cost: random numbers–in average, tj = j/2. T(n) will still be in the order of n2, same as the worst case.8Merge Sort—divide-and-conquer•Divide: divide the n-element sequence into two subproblems of n/2 elements each.•Conquer: sort the two subsequences recursively using merge sort. If the length of a sequence is 1, do nothing since it is already in order.•Combine: merge the two sorted subsequences to produce the sorted answer.9Merge Sort –merge function•Merge is the key operation in merge sort.•Suppose the (sub)sequence(s) are stored in the array A. moreover, A[p..q] and A[q+1..r] are two sorted subsequences.•MERGE(A,p,q,r) will merge the two subsequences into sorted sequence A[p..r]–MERGE(A,p,q,r) takes (r-p+1).10MERGE-SORT(A,p,r)1. if p < r2. then q  (p+r)/23. MERGE-SORT(A,p,q)4. MERGE-SORT(A,q+1,r)5. MERGE(A,p,q,r)Call to MERGE-SORT(A,1,n) (suppose n=length(A))11Analysis of Divide-and-Conquer•Described by recursive equation•Suppose T(n) is the running time on a problem of size n.•T(n) = (1) if nnc aT(n/b)+D(n)+C(n) if n> ncWhere a: number of subproblems n/b: size of each subproblem D(n): cost of divide operation C(n): cost of combination operation12Analysis of MERGE-SORT•Divide: D(n) = (1)•Conquer: a=2,b=2, so 2T(n/2)•Combine: C(n) = (n)•T(n) = (1) if n=1 2T(n/2)+ (n) if n>1•T(n) = c if n=1 2T(n/2)+ cn if n>113Compute T(n) by Recursive Tree•The recursive equation can be solved by recursive tree.•T(n) = 2T(n/2)+ cn, (See its Recursive Tree).•lg n+1 levels, cn at each level, thus•Total cost for merge sort is –T(n) =cnlg n +cn = (nlg n).–Question: best, worst, average?•In contrast, insertion sort is – T(n) = (n2).14Recursion tree of T(n)=2T(n/2)+cn15Order of growth•Lower order item(s) are ignored, just keep the highest order item.•The constant coefficient(s) are ignored.•The rate of growth, or the order of growth, possesses the highest significance. •Use (n2) to represent the worst case running time for insertion sort.•Typical order of growth: (1), (lg n), (n),(n), (nlg n), (n2), (n3), (2n), (n!)•Asymptotic notations: , O, , o, .16f(n) = ( g(n))nn0c1g(n)c2g(n)f(n)f(n) = O( g(n))nn0f(n)cg(n)f(n) = ( g(n))nn0cg(n)f(n)There exist positive constants c1 and c2such that there is a positive constant n0such that …There exist positive constants csuch that there is a positive constant n0such that …There exist positive constants csuch that there


View Full Document

IUPUI CS 580 - Introduction to Algorithm design and analysis

Download Introduction to Algorithm design and analysis
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Introduction to Algorithm design and analysis and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Introduction to Algorithm design and analysis 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?