Tuesday 2 July 2013

Analysis of Algorithms


Adapted from the Goodrich and Tamassia viewgraphs on Analysis of Algorithms


A Quick Math Review
  • Logarithms and exponents
    • properties of logarithms:
    • properties of exponentials:

A Quick Math Review (cont.)
  • Floor
  • Ceiling
  •  
  • Summations
    • general definition:
    • where f is a function, s is the start index, and t is the end index.
  • Geometric progression:
    • a summation where f(i) = ai
    • given an integer  and a real number ,
    • geometric progressions exhibit exponential growth.

A Quick Math Review (cont.)
  • Arithmetic progressions:
    • An example
    • two visual representations


Forward Proof of Geometric Progression
                                     (1)
Multiply (1) by –a
                            (2)
Add (1) and (2)
Divide by (1-a)
Special case of a=2:


Simple Justification Techniques




By Example: Can only be used to justify claims of a generic nature. Often part of a larger justification.
Claim: $ real numbers c > 0 and n0 ³ 1 for which 
Justification: Choose n0 = 1 and c = 7.
 
By Counter-Example:To disprove a bogus claim, a counter-example is all that is necessary.
False claim: Every number 2i – 1, where i is a positive integer, is a prime number.
Disproof: 24 – 1 = 16 – 1 = 15 = 5× 3, which is not a prime number. Therefore the claim is not true.



Simple Justification Techniques (cont.)




By Contradiction – Suppose that the claim is not true. Show that this assumption leads to an inconsistency.
Claim: There is no biggest positive integer.
Justification: Suppose B is the biggest positive integer. Now let A = B + 1. Note that A > B.
Þ B cannot be the biggest positive integer.
 
Contra-Positive:
Claim: If A is true then B is true.
Justification: Show that if B is not true then A cannot be true.

Proofs by Induction
Show that property P is true for all integers .
Basis: Prove that P is true for n0.
Inductive hypothesis: Assume that P is true for all . Prove that P is also true for k = n.
Example: arithmetic progression
.
Basis: S(1) = 1(1 + 1)/2 = 1. OK
Inductive hypothesis: .

Advanced Topics: Other Justification Techniques
  • Proof by excessive waving of hands.
  • Proof by incomprehensible diagrams.
  • Proof by very large bribes.
    • See instructor after class.
  • The Emperor's New Clothes Method
    • "This proof is so obvious that only an idiot wouldn't be able to understand it.

Measuring the Running Time
  • How should we measure the running time of an algorithm?
  • Experimental Study
    • Write a program that implements the algorithm.
    • Run the program with data sets of varying size and composition.
    • Use a method like System.currentTimeMillis() to get an accurate measure of the actual running time.
    • The resulting data set should look something like:

Beyond Experimental Studies
  • Experimental studies have several limitations:
    • It is necessary to implement and test the algorithm in order to determine its running time.
    • Experimental studies can be done only on a limited set of inputs and may not be indicative of the running time on other inputs not included in the experiment.
    • In order to compare two algorithms, the same hardware and software environments should be used.
  • We shall now develop a general methodology for analyzing the running time of algorithms that
    • Uses a high-level description of the algorithm instead of testing one of its implementations.
    • Takes into account all possible inputs.
    • Allows us to evaluate the efficiency of any algorithm in a manner that is independent from the hardware and software environment.



What is Pseudo-Code?
  • A mixture of natural language and high-level programming concepts that describes the main ideas behind a generic implementation of a data structure or algorithm.
    • Expressions: use standard mathematical symbols to describe numeric and boolean expressions.
      • use ¬ for assignment ("=" in Java).
      • use = or == for equality testing ("==" in Java).
    • Method declarations:
      • Algorithm name(param1, param2)
    • Programming constructs:
      • decision constructs: if … then … [else …]
      • while loops: while … do
      • repeat loops: repeat … do
      • for loops: for … do
      • array indexing A[i]
    • Methods (Algorithms):
      • calls: name(args…)
      • returns: return value

Pseudo-Code (cont.)
  • Pseudo-code is a description of an algorithm that is more structured than prose but less formal than a programming language.
  • Example: finding the maximum element of an array.
Algorithm arrayMax(A, n):
Input: An array A storing n integers
Output: The maximum element in A. currentMax ¬ A[0]
for i ¬ 1 to n-1 do if currentMax < A[i] then currentMax ¬A[i] return currentMax
  • Pseudo-code is our preferred notation for describing algorithms.
  • However, pseudo-code hides some program design and implementation issues.

Analysis of Algorithms
  • Primitive Operation: Low-level computations that are largely independent from the programming language and can be identified in pseudocode, e.g.
    • calling a method and returning from a method
    • performing an arithmetic operation (e.g., addition or subtraction).
    • comparing two numbers
    • indexing into an array
    • following an object method
    • returning from a method.
  • By inspecting the pseudo-code, we can count the number of primitive operations executed by an algorithm.
  • Recall the arrayMax example (previous viewgraph).

Average Case vs. Worst Case Running Time of an Algorithm
  • An algorithm may run faster on certain data sets than on others.
  • Finding the average case can be very difficult, so typically algorithms are measured by worst-case time complexity.
  • Also, in certain applications domains (e.g., air traffic control, surgery) knowing the worst-case time complexity is of crucial importance.


Asymptotic Notation
Big-Oh:
  • Given
    • Functions f and g defined over non-negative integers, and
    • real constants c and n0,
  • we define big-Oh as follows:


Examples of Big-Oh
Example: 7n – 3 is O(n)
Justification:
satisfies this inequality.

Example:
Justification:
$ c,n0 such that

Since
we can write

Thus c = 35 and n0 = 1.



Asymptotic Notation (cont.)
  • Note: Even though it is true that 7n-3 is O(n5), the big-Oh characterization should be of as small an order as possible.
  • Simple Rule: Drop lower order terms and constant factors.
  • Special classes of algorithms:
    • constant time   O(1)
    • logarithmic      O(log n)
    • linear              O(n)
    • n log n            O(n log n)
    • quadratic        O(n2)
    • polynomial      O(nk), k > 1
    • exponential     O(an), n > 1
  • "Relatives" of big-Oh:
    • W (g(n)): big Omega
    • Q (g(n)): big Theta

Big Omega
Definition:

Illustration:

 

Big Theta
Definition:

Illustration


Asymptotic Analysis of Running Time
  • Use the big-Oh notation to express the number of primitive operations executed as a function of the input size n.
  • For example, we say that the arrayMax algorithm runs in O(n) time.
  • Comparing the asymptotic running time,
    • an algorithm that runs in O(n) time is generally better than one that runs in O(n2) time.
    • similarly, O(log n) is generally better than O(n).
    • heirarchy of functions:
  • Caution!
    • Beware of very large constant factors. An algorithm that runs in time 109n is still O(n) but might be less efficient on your dataset than one runnning in time 2n2, which is O(n2).






Example of Asymptotic Analysis (1)
  • An algorithm for computing prefix averages:
Algorithm prefixAverages1(X)
Input: An n-element array X of numbers.
Output: An n-element array A of numbers such that A[i] is the average of elements X[0], …, X[i]. Let A be an array of n numbers.
for i ¬ 0 to n-1 do a ¬ 0
for j ¬ 0 to i do a ¬a + X[j] A[i] ¬a/(i+1)
return array A
    • Analysis …

  • Example of Asymptotic Analysis (2)
    • An improved algorithm for computing prefix averages:
    Algorithm prefixAverages2(X)
    Input: An n-element array X of numbers.
    Output: An n-element array A of numbers such that A[i] is the average of elements X[0], …, X[i]. Let A be an array of n numbers.
    s ¬ 0
    for i ¬ 0 to n-1 do s ¬s + X[i]
    A[i] ¬s/(i+1)
    return array A
      • Analysis …

    No comments:

    Post a Comment