DOC PREVIEW
UNL CSCE 235 - Algorithm Analysis

This preview shows page 1 out of 3 pages.

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

Unformatted text preview:

Algorithm AnalysisSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Section 3.3 of [email protected] can we say that one algorithm performs better than another?Quantify the resources required to execute:ITimeIMemoryII/OIcircuits, power, etcTime is not merely CPU clock c ycle s, we want to study algorithmsindependent or implementations, platforms, and hardware. Weneed an objective point of reference. For that, we measure time by“the number of operations as a function of an algorithm’s inputsize.”Input SizeFor a given problem, we characterize the input size, n,appropriately:ISorting – The number of items to be sortedIGraphs – The number of vertices and/or edgesINumerical – The number of bits needed to represent a numberThe choice of an input size greatly depends on the eleme ntaryoperation; the most relevant or important operation of analgorithm.IComparisonsIAdditionsIMultiplicationsOrders of GrowthSmall input sizes can usually be computed instantaneously, thus weare most intereste d in how an algorithm performs as n → ∞.Indeed, for small values of n, most s uch functions will be verysimilar in running time. Only for sufficiently large n do differencesin running time become apparent. As n → ∞ the differencesbecome more and more stark.IntractabilityProblems that we can solve (today) only with exponential orsuper-exponential time algorithms are said to be (likely)intractable. That is, though they may be solved in a reasonableamount of time for small n, for large n, there is (likely) no hope ofefficient execution. It may take millions or billions of years.Tractable problems are problems that have efficient (read:polynomial) algorithms to solve them. Polynomial order ofmagnitude usually means there exists a polynomial p(n) = nkforsome constant k that always bounds the order of growth. More onasymptotics in the next slide set.Intractable problems may need to be solve d using approximation orrandomized algorithms.Worst, Best, and Average CaseSome algorithms perform differently on various inputs of similarsize. It is sometimes helpful to consider the Worst-Case, Best-Case,and Average-Case efficiencies of algorithms. For example, say wewant to search an array A of size n for a given value K.IWorst-Case: K 6∈ A then we must search every item (ncomparisons)IBest-Case: K is the first item that we check, so only onecomparisonAverage-CaseSince any worth-while algorithm will be used quite extensively, theaverage running-time is arguably the best measure of itsperformance (if the worst-case is not frequently encountered). Forsearching an array, and assuming that p is the probability of asuccessful search, we have:Cavg(n) =p + 2p + . . . + ip + . . . npn+ n(1 − p)=pn(1 + 2 + . . . + i + . . . + n) + n(1 − p)=pn(n(n + 1)2+ n(1 − p)If p = 1 (search succeeds), Cavg(n) =n+12≈ .5n.If p = 0 (search fails), Cavg(n) = n.A more intuitive interpretation is that the algorithm m ust e xamine,on average, half of all elements in A.Average-CaseAverage-Case analysis of algorithms is important in a practicalsense. Often, Cavgand Cworsthave the same order of magnitudeand thus, from a theoretical point of view, are no different fromeach other. Practical implementations, however, require areal-world examination.Mathematical Analysis of AlgorithmsAfter developing pseudo-code for an algorithm, we wish to analyzeits efficiency as a function of the size of the input, n in terms ofhow many times the elementary operation is performed. Here is ageneral strategy:1. Decide on a parameter(s) for the input, n.2. Identify the basic operation.3. Evaluate if the elementary operation depends only on n(otherwise evaluate best, worst, and average-case separately.4. Set up a summation corresponding to the number ofelementary operations5. Simplify the equation to get as simple of a function f (n) aspossible.Analysis ExamplesExample IConsider the following code.Algorithm (UniqueElements)Input : Integer array A of size nOutput : true if all elements a ∈ A are distinctfor i = 1, . . . , n − 1 do1for j = i + 1, . . . , n do2if ai= ajthen3return false4end5end6end7return true8Analysis ExampleExample I - AnalysisFor this algorithm, what isIThe elementary operation?IInput Size?IDoes the elem entary operation depend only on n?The outer for-loop is run n − 1 times. More formally, it contributesn−1Xi=1Analysis ExampleExample I - AnalysisThe inner for-loop depends on the outer for-loop, so it contributesnXj=i+1We observe t hat the ele mentary operation is exe cuted onc e in e achiteration, thus we haveCworst(n) =n−1Xi=1nXj=i+11 =n(n − 1)2Analysis ExampleExample IIThe parity of a bit string determines whether or not the number of1s appearing in it is even or odd. It is used as a simple form oferror correction over communication networks.Algorithm (Parity)Input : An integer n in binary (b[])Output : 0 if the parity of n is even, 1 otherwiseparity ← 01while n > 0 do2if b[0] = 1 then3parity ← parity + 1 mod 24right-shift(n)5end6end7return parity8Analysis ExampleExample II - AnalysisFor this algorithm, what isIThe elementary operation?IInput Size?IDoes the elem entary operation depend only on n?The while-loop will be executed as many times as there are 1-bitsin its binary representation. In the worst case, we’ll have a bitstring of all ones.The number of bits required to represent an integer n isdlog neso the running time is simply log n.Analysis ExampleExample IIIAlgorithm (MyFunction(n, m, p))Input : Integers n, m, p such that n > m > pOutput : Some function f(n, m, p)x = 11for i = 0, . . . , 10 do2for j = 0, . . . , n do3for k = m/2, . . . , m do4x = x × p5end6end7end8return x9Analysis ExampleExample III - AnalysisIOuter Loop: executed 11 times.I2nd Loop: executed n + 1 times.IInner Loop: executed aboutm2times.IThus we haveC(n, m, p) = 11(n + 1)(m/2)IBut, do we really need to consider p?Summation Tools ISection 2.4 (p157) has more summation rules. You can always useMaple to evaluate and simplify complex expressions (but know howto do them by hand!).To invoke maple, on cse you can use the command-line interfaceby typing maple. Under unix (gnome or KDE) or via any xwindowsinterface, you can use the graphical version via xmaple.Will be demonstrated during recitation.Summation Tools IIExample> simplify(sum(i, i=0..n));12n2+12n> Sum(Sum(j, j=i..n),


View Full Document

UNL CSCE 235 - Algorithm 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 Algorithm 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 Algorithm 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 Algorithm 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?