DOC PREVIEW
UNL CSCE 235 - Algorithms Analysis

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 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 25 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 25 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 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Algorithms AnalysisOutlineIntroductionInput SizeSlide 5Order of GrowthIntractabilityWorst, Best, and Average CaseAverage-Case: ExampleAverage-Case: ImportanceSlide 11Mathematical Analysis of AlgorithmsAlgorithm Analysis: Example 1 (1)Algorithm Analysis: Example 1 (2)Algorithm Analysis: Example 1 (3)Computing i=1n-1 j=i+1n 1Algorithm Analysis: Example 2 (1)Algorithm Analysis: ParityCheckingAlgorithm Analysis: Example 2 (2)Algorithm Analysis: Example 3 (1)Algorithm Analysis: Example 3 (2)Slide 22Summation ToolsSummation Tools: MapleSummaryAlgorithms AnalysisSection 3.3 of RosenFall 2008CSCE 235 Introduction to Discrete StructuresCourse web-page: cse.unl.edu/~cse235Questions: [email protected] AnalysisCSCE 235, Fall 20082Outline•Introduction•Input Size•Order of Growth•Intractability•Worst, Best, and Average Cases•Mathematical Analysis of Algorithms–3 Examples•Summation toolsAlgorithm AnalysisCSCE 235, Fall 20083Introduction•How can we say that one algorithm performs better than another one?•Quantify the resources needed to run it:–Time–Memory–I/O, disk access–Circuit, power, etc.•Time is not merely CPU clock cycle–We want to study algorithms independent of implementations, platforms, and hardware.–We need an objective point of reference–For that we measure time by the number of operations as a function of the size of the input to the algorithmAlgorithm AnalysisCSCE 235, Fall 20084Input Size•For a given problem, we characterize the input size n appropriately–Sorting: The number of items to be sorted–Graphs: The number of vertices and/or edges–Matrix manipulation: The number of rows and colums–Numerical operations: the number of bits needed to represent a number•The choice of an input size greatly depends on the elementary operation: the most relevant or important operation of an algorithm–Comparisons–Additions–MultiplicationsAlgorithm AnalysisCSCE 235, Fall 20085Outline•Introduction•Input Size•Order of Growth•Intractability•Worst, Best, and Average Cases•Mathematical Analysis of Algorithms–3 Examples•Summation toolsAlgorithm AnalysisCSCE 235, Fall 20086Order of Growth•Small input sizes can usually be computed instantaneously, thus we are most interested in how an algorithms performs as n •Indeed, for small values of n, most such functions will be very similar in running time.•Only for sufficiently large n do differences in running time become apparent:As n the differences become more and more starkAlgorithm AnalysisCSCE 235, Fall 20087Intractability•Problems that we can solve (today) only with exponential or super-exponential time algorithms are said to be (likely) intractable. That is, though they may be solved in a reasonable amount of time for small n, for large n, there is (likely) no hope for efficient execution. It may take millions or billions of years.•Tractable problems are problems that have efficient (read: polynomial) algorithms to solve them.•Polynomial order of magnitude usually means that there exists a polynomial p(n)=nk for some constant k that always bounds the order of growth. More on asymptotics in the next lecture•Intractable problems may need to be solved using approximation or randomized algorithms (except for small size of input)Algorithm AnalysisCSCE 235, Fall 20088Worst, Best, and Average Case•Some algorithms perform differently on various input of similar size. It is sometimes helpful to consider–The worst-case–The best-case–The average-casePerformance of the algorithm.•For example, say we want to search an array A of size n for a given value k–Worst-case: kA, then we must check every item. Cost= n comparisons–Best-case: k is the first item in the array. Cost=1 comparison–Average-case: Probabilistic analysisAlgorithm AnalysisCSCE 235, Fall 20089Average-Case: Example•Since any worthwhile algorithm will be used quite extensively, the average running time is arguably the best measure of the performance of the algorithm (if the worst case is not frequently encountered).•For searching an array and assuming that p is the probability of a successful search we haveCaverage(n) = (p+2p+…+ip+…+np)/n + n(1-p) = (1+2+…+i+n) p/n+n(1-p) = (n(n+1)/2) p/n +n(1-p)=p(n+1)/2+n(1-p)–If p=0 (search fails), Caverage(n) =n–If p=1 (search succeeds), Caverage(n) =(n+1)/2 n/2Intuitively, the algorithm must examine on average half of all the elements in AAlgorithm AnalysisCSCE 235, Fall 200810Average-Case: Importance•Average-case analysis of algorithms is important in a practical sense.•Often Cavg and Cworst have the same order of magnitude and thus from a theoretical point of view, are no different from each other•Practical implementations, however, require a real-world examination and empirical analysisAlgorithm AnalysisCSCE 235, Fall 200811Outline•Introduction•Input Size•Order of Growth•Intractability•Worst, Best, and Average Cases•Mathematical Analysis of Algorithms–3 Examples•Summation toolsAlgorithm AnalysisCSCE 235, Fall 200812Mathematical Analysis of Algorithms•After developing a pseudo-code for an algorithm, we wish to analyze its performance –as a function of the size of the input, n, –in terms of how many times the elementary operation is performed.•Here is a general strategy1. Decide on a parameter(s) for the input, n2. Identify the basic operation3. Evaluate if the elementary operation depends only on n4. Set up a summation corresponding to the number of elementary operations5. Simplify the equation to get as simple of a function f(n) as possibleAlgorithm AnalysisCSCE 235, Fall 200813Algorithm Analysis: Example 1 (1)UniqueElementsInput: Integer array A of size nOutput: True if all elements a  A are distinct1. For i=1,…, (n-1) Do2. For j=i+1,…,n Do3. If ai=aj 4. Then Return false5. End6. End7. End8. Return trueAlgorithm AnalysisCSCE 235, Fall 200814Algorithm Analysis: Example 1 (2)•For this algorithm, what is–The elementary operation?–Input size?–Does the elementary operation depend only on n?•The outer for-loop runs n-1 times. More formally it contributes: i=1n-1•The inner for-loop depends on the outer for-loop and contributes: j=i+1n– Comparing ai and aj–n, size of AAlgorithm AnalysisCSCE 235, Fall 200815Algorithm Analysis: Example 1 (3)•We observe that the elementary operation is executes once in each iteration,


View Full Document

UNL CSCE 235 - Algorithms Analysis

Documents in this Course
Logic

Logic

77 pages

Proofs

Proofs

82 pages

Induction

Induction

85 pages

Proofs

Proofs

52 pages

Sets

Sets

8 pages

Recursion

Recursion

16 pages

Proofs

Proofs

82 pages

Functions

Functions

71 pages

Recursion

Recursion

50 pages

Functions

Functions

54 pages

Graphs

Graphs

56 pages

Induction

Induction

32 pages

Relations

Relations

60 pages

Graphs

Graphs

10 pages

Recursion

Recursion

80 pages

Recursion

Recursion

81 pages

Functions

Functions

16 pages

Recursion

Recursion

16 pages

Sets

Sets

52 pages

Relations

Relations

60 pages

Load more
Download Algorithms 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 Algorithms 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 Algorithms 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?