logging in or signing up Analysis & Design of Algorithms shweta.mundra Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 766 Category: Education License: All Rights Reserved Like it (4) Dislike it (0) Added: February 01, 2010 This Presentation is Public Favorites: 3 Presentation Description Complexity & Introduction of Algorithm Comments Posting comment... By: anithadmello7 (18 month(s) ago) excellent Saving..... Post Reply Close Saving..... Edit Comment Close By: ygsupreeth (20 month(s) ago) Execellent Presentation Saving..... Post Reply Close By: shweta.mundra (20 month(s) ago) Thanks a lot Saving..... Edit Comment Close Premium member Presentation Transcript Complexity & Growth Order : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Complexity & Growth Order The Algorithm : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Algorithm: “A finite set of unambiguous instructions performed in a prescribed sequence to achieve a goal” The Algorithm Tomato Soup Recipe (Algorithm) : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Tomato Soup Recipe (Algorithm) 1. Gather Ingredients 2. Combine sugar (1tbs), salt (1tbs), Clarified Butter (1tbs), flour(1c) ,Tomato (3-4)in mixing bowl 3. Turn on mixer & Grind Tomato finely 4. Add 1/4 cup of flour 5. If grind properly go to step 6, otherwise go back to step 4 6. Boil 15 minutes 7. Let rest for at least 5 minutes in warm area Tomato Soup Recipe for N Bowls (Algorithm) : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Tomato Soup Recipe for N Bowls (Algorithm) 1. Gather Ingredients 2. Combine sugar (N tbs), salt (N tbs), Clarified Butter (N tbs), Maida (Nc) ,Tomato (N)in mixing bowl 3. Turn on mixer & Grind Tomato finely 4. Add N/4 cup of flour 5. If grind properly go to step 6, otherwise go back to step 4 6. Boil 15 minutes 7. Let rest for at least 5 minutes in warm area Tomato Soup Recipe for N Bowls (Algorithm) : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Tomato Soup Recipe for N Bowls (Algorithm) 1. Gather Ingredients 2. Combine sugar (N tbs), salt (N tbs), Clarified Butter (N tbs), Maida (Nc) ,Tomato (N)in mixing bowl 3. Turn on mixer & Grind Tomato finely 4. Add N/4 cup of flour 5. If Grind properly go to step 6, otherwise go back to step 4 6. Boil 15 minutes 7. Let rest for at least 5 minutes in warm area N Soup Bowls Variable Sequence of Statements Tomato Soup Recipe for N Bowls (Algorithm) : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Tomato Soup Recipe for N Bowls (Algorithm) 1. Gather Ingredients 2. Combine sugar (N tbs), salt (N tbs), Clarified Butter (N tbs), Maida (Nc) ,Tomato (N)in mixing bowl 3. Turn on mixer & Grind Tomato finely 4. Add N/4 cup of flour 5. If Grind properly go to step 6, otherwise go back to step 4 6. Boil 15 minutes 7. Let rest for at least 5 minutes in warm area N Soup Bowls Conditional Tomato Soup Recipe for N Bowls (Algorithm) : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Tomato Soup Recipe for N Bowls (Algorithm) 1. Gather Ingredients 2. Combine sugar (N tbs), salt (N tbs), Clarified Butter (N tbs), Maida (Nc) ,Tomato (N)in mixing bowl 3. Turn on mixer & Grind Tomato finely 4. Add N/4 cup of flour 5. If Grind properly go to step 6, otherwise go back to step 4 6. Boil 15 minutes 7. Let rest for at least 5 minutes in warm area N Soup Bowls Subroutines Mini-algorithms Algorithm Must satisfy following Criteria : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Algorithm Must satisfy following Criteria Input Output Definiteness Finiteness Effectiveness Study of Algorithm includes following area : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Study of Algorithm includes following area How to devise algorithm? How to validate algorithm? How to analyze algorithm? How to test a program? Program PerformanceAnalysis : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Program PerformanceAnalysis Criteria for Measurement : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Criteria for Measurement Space amount of memory program occupies usually measured in bytes, KB or MB Time execution time usually measured by the number of executions Space Complexity : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Space Complexity Space complexity is defined as the amount of memory a program needs to run to completion. Why is this of concern? We could be running on a multi-user system where programs are allocated a specific amount of space. We may not have sufficient memory on our computer. There may be multiple solutions, each having different space requirements. The space complexity may define an upper bound on the data that the program can handle. Components of Program Space : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Components of Program Space Program space = Instruction space + data space + stack space The instruction space is dependent on several factors. the compiler that generates the machine code the target computer Components of Program Space : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Components of Program Space Data space very much dependent on the computer architecture and compiler The magnitude of the data that a program works with is another factor char 1 float 4short 2 double 8int 2 long double 10long 4 pointer 2 Unit: bytes Components of Program Space : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Components of Program Space Data space Choosing a “smaller” data type has an effect on the overall space usage of the program. Choosing the correct type is especially important when working with arrays. Components of Program Space : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Components of Program Space Environment Stack Space Every time a function is called, the following data are saved on the stack. the return address the values of all local variables and value formal parameters the binding of all reference and const reference parameters Space Complexity Summary : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Space Complexity Summary Some points for efficient space utilization Always choose the optimal (smallest necessary) data type Study the compiler. Learn about the effects of different compilation settings. Choose non-recursive algorithms when appropriate. Time Complexity : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Time Complexity Time complexity is the amount of computer time a program needs to run. Why do we care about time complexity? Some computers require upper limits for program execution times. Some programs require a real-time response. If there are many solutions to a problem, typically we’d like to choose the quickest. Time Complexity : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Time Complexity How do we measure? Count a particular operation (operation counts) Count the number of steps (step counts) Asymptotic complexity Running Example : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Running Example Algorithm Sum(a,n) { s:=0.0; for i=1 to n do s:= s+ a[i]; return s; } The number of sum depends on n. Operation Count : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Operation Count Worst case count = maximum count Best case count = minimum count Average count Step Count : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Step Count The operation-count method omits accounting for the time spent on all but the chosen operation The step-count method count for all the time spent in all parts of the program A program step is loosely defined to be a syntactically or semantically meaningful segment of a program for which the execution time is independent of the instance characteristics. 100 adds, 100 subtracts, 1000 multiples can be counted as one step. However, n adds cannot be counted as one step. Step Count : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Step Count steps/execution (s/e) Algorithm Sum(a,n) 0 { 0 s:=0.0; 1 for i=1 to n do 1 s:= s+ a[i]; 1 return s; 1 } Step Count : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Step Count s/e Frequency Algorithm Sum(a,n) 0 0 { 0 0 s:=0.0; 1 1 for i=1 to n do 1 n+1 s:= s+ a[i]; 1 n return s; 1 1 } 0 0 Step Count : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Step Count Total step counts = 0+0+1+(n+1)+n+1+0 = 2n + 3 Slide 26: Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Two important reasons to determine operation and step counts To compare the time complexities of two programs that compute the same function To predict the growth in run time as the instance characteristic changes Neither of the two yield a very accurate measure Operation counts: focus on “key” operations and ignore all others Step counts: the notion of a step is itself inexact You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
Analysis & Design of Algorithms shweta.mundra Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 766 Category: Education License: All Rights Reserved Like it (4) Dislike it (0) Added: February 01, 2010 This Presentation is Public Favorites: 3 Presentation Description Complexity & Introduction of Algorithm Comments Posting comment... By: anithadmello7 (18 month(s) ago) excellent Saving..... Post Reply Close Saving..... Edit Comment Close By: ygsupreeth (20 month(s) ago) Execellent Presentation Saving..... Post Reply Close By: shweta.mundra (20 month(s) ago) Thanks a lot Saving..... Edit Comment Close Premium member Presentation Transcript Complexity & Growth Order : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Complexity & Growth Order The Algorithm : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Algorithm: “A finite set of unambiguous instructions performed in a prescribed sequence to achieve a goal” The Algorithm Tomato Soup Recipe (Algorithm) : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Tomato Soup Recipe (Algorithm) 1. Gather Ingredients 2. Combine sugar (1tbs), salt (1tbs), Clarified Butter (1tbs), flour(1c) ,Tomato (3-4)in mixing bowl 3. Turn on mixer & Grind Tomato finely 4. Add 1/4 cup of flour 5. If grind properly go to step 6, otherwise go back to step 4 6. Boil 15 minutes 7. Let rest for at least 5 minutes in warm area Tomato Soup Recipe for N Bowls (Algorithm) : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Tomato Soup Recipe for N Bowls (Algorithm) 1. Gather Ingredients 2. Combine sugar (N tbs), salt (N tbs), Clarified Butter (N tbs), Maida (Nc) ,Tomato (N)in mixing bowl 3. Turn on mixer & Grind Tomato finely 4. Add N/4 cup of flour 5. If grind properly go to step 6, otherwise go back to step 4 6. Boil 15 minutes 7. Let rest for at least 5 minutes in warm area Tomato Soup Recipe for N Bowls (Algorithm) : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Tomato Soup Recipe for N Bowls (Algorithm) 1. Gather Ingredients 2. Combine sugar (N tbs), salt (N tbs), Clarified Butter (N tbs), Maida (Nc) ,Tomato (N)in mixing bowl 3. Turn on mixer & Grind Tomato finely 4. Add N/4 cup of flour 5. If Grind properly go to step 6, otherwise go back to step 4 6. Boil 15 minutes 7. Let rest for at least 5 minutes in warm area N Soup Bowls Variable Sequence of Statements Tomato Soup Recipe for N Bowls (Algorithm) : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Tomato Soup Recipe for N Bowls (Algorithm) 1. Gather Ingredients 2. Combine sugar (N tbs), salt (N tbs), Clarified Butter (N tbs), Maida (Nc) ,Tomato (N)in mixing bowl 3. Turn on mixer & Grind Tomato finely 4. Add N/4 cup of flour 5. If Grind properly go to step 6, otherwise go back to step 4 6. Boil 15 minutes 7. Let rest for at least 5 minutes in warm area N Soup Bowls Conditional Tomato Soup Recipe for N Bowls (Algorithm) : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Tomato Soup Recipe for N Bowls (Algorithm) 1. Gather Ingredients 2. Combine sugar (N tbs), salt (N tbs), Clarified Butter (N tbs), Maida (Nc) ,Tomato (N)in mixing bowl 3. Turn on mixer & Grind Tomato finely 4. Add N/4 cup of flour 5. If Grind properly go to step 6, otherwise go back to step 4 6. Boil 15 minutes 7. Let rest for at least 5 minutes in warm area N Soup Bowls Subroutines Mini-algorithms Algorithm Must satisfy following Criteria : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Algorithm Must satisfy following Criteria Input Output Definiteness Finiteness Effectiveness Study of Algorithm includes following area : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Study of Algorithm includes following area How to devise algorithm? How to validate algorithm? How to analyze algorithm? How to test a program? Program PerformanceAnalysis : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Program PerformanceAnalysis Criteria for Measurement : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Criteria for Measurement Space amount of memory program occupies usually measured in bytes, KB or MB Time execution time usually measured by the number of executions Space Complexity : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Space Complexity Space complexity is defined as the amount of memory a program needs to run to completion. Why is this of concern? We could be running on a multi-user system where programs are allocated a specific amount of space. We may not have sufficient memory on our computer. There may be multiple solutions, each having different space requirements. The space complexity may define an upper bound on the data that the program can handle. Components of Program Space : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Components of Program Space Program space = Instruction space + data space + stack space The instruction space is dependent on several factors. the compiler that generates the machine code the target computer Components of Program Space : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Components of Program Space Data space very much dependent on the computer architecture and compiler The magnitude of the data that a program works with is another factor char 1 float 4short 2 double 8int 2 long double 10long 4 pointer 2 Unit: bytes Components of Program Space : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Components of Program Space Data space Choosing a “smaller” data type has an effect on the overall space usage of the program. Choosing the correct type is especially important when working with arrays. Components of Program Space : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Components of Program Space Environment Stack Space Every time a function is called, the following data are saved on the stack. the return address the values of all local variables and value formal parameters the binding of all reference and const reference parameters Space Complexity Summary : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Space Complexity Summary Some points for efficient space utilization Always choose the optimal (smallest necessary) data type Study the compiler. Learn about the effects of different compilation settings. Choose non-recursive algorithms when appropriate. Time Complexity : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Time Complexity Time complexity is the amount of computer time a program needs to run. Why do we care about time complexity? Some computers require upper limits for program execution times. Some programs require a real-time response. If there are many solutions to a problem, typically we’d like to choose the quickest. Time Complexity : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Time Complexity How do we measure? Count a particular operation (operation counts) Count the number of steps (step counts) Asymptotic complexity Running Example : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Running Example Algorithm Sum(a,n) { s:=0.0; for i=1 to n do s:= s+ a[i]; return s; } The number of sum depends on n. Operation Count : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Operation Count Worst case count = maximum count Best case count = minimum count Average count Step Count : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Step Count The operation-count method omits accounting for the time spent on all but the chosen operation The step-count method count for all the time spent in all parts of the program A program step is loosely defined to be a syntactically or semantically meaningful segment of a program for which the execution time is independent of the instance characteristics. 100 adds, 100 subtracts, 1000 multiples can be counted as one step. However, n adds cannot be counted as one step. Step Count : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Step Count steps/execution (s/e) Algorithm Sum(a,n) 0 { 0 s:=0.0; 1 for i=1 to n do 1 s:= s+ a[i]; 1 return s; 1 } Step Count : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Step Count s/e Frequency Algorithm Sum(a,n) 0 0 { 0 0 s:=0.0; 1 1 for i=1 to n do 1 n+1 s:= s+ a[i]; 1 n return s; 1 1 } 0 0 Step Count : Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Step Count Total step counts = 0+0+1+(n+1)+n+1+0 = 2n + 3 Slide 26: Presented By:Shweta Bajaj Lecturer,MCA Medicaps Indore(M.P.) Two important reasons to determine operation and step counts To compare the time complexities of two programs that compute the same function To predict the growth in run time as the instance characteristic changes Neither of the two yield a very accurate measure Operation counts: focus on “key” operations and ignore all others Step counts: the notion of a step is itself inexact