Scribd Logo
Upload

Welcome to Scribd!

  • 26 views

    Chapter 5: Probabilistic Analysis

    Uploaded by

    Debasish Halder
    The document discusses average-case analysis of algorithms. It provides two examples: 1) Finding the maximum element in an array, which has an average-case running time of O(n) because the maximum element has a 1/n probability of being compared on each iteration. 2) Randomly permuting an array in-place, which runs in O(n) time and randomly reorders the array through a series of swaps.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Chapter 5: Probabilistic Analysis

    Uploaded by

    Debasish Halder
    26 views2 pages
    The document discusses average-case analysis of algorithms. It provides two examples: 1) Finding the maximum element in an array, which has an average-case running time of O(n) because the maximum element has a 1/n probability of being compared on each iteration. 2) Randomly permuting an array in-place, which runs in O(n) time and randomly reorders the array through a series of swaps.

    Original Description:

    low power

    Original Title

    Prob Analysishandout

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document discusses average-case analysis of algorithms. It provides two examples: 1) Finding the maximum element in an array, which has an average-case running time of O(n) because the maximum element has a 1/n probability of being compared on each iteration. 2) Randomly permuting an array in-place, which runs in O(n) time and randomly reorders the array through a series of swaps.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    26 views2 pages

    Chapter 5: Probabilistic Analysis

    Uploaded by

    Debasish Halder
    The document discusses average-case analysis of algorithms. It provides two examples: 1) Finding the maximum element in an array, which has an average-case running time of O(n) because the maximum element has a 1/n probability of being compared on each iteration. 2) Randomly permuting an array in-place, which runs in O(n) time and randomly reorders the array through a series of swaps.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 2

    Average-Case Analysis

    Chapter 5: Probabilistic Analysis


    Average-Case Analysis Finding the Maximum Example Randomizing an Array Example

    In practice, many algorithms perform better than their worst-case. The average case is analyzed by: 1. construct a probabilistic model of the input 2. determine the probabilities and running times (or costs) of alternate executions 3. calculate expected running time (or cost) Through randomization, one can often ensure that the probabilisitic model is true.
    CS 5633 Analysis of Algorithms Chapter 5: Slide 2

    Example 1: Finding the Maximum


    Average-Case Analysis . . . . . . . . . . . . . . . . Example 1: Finding the Maximum . . . . . . . . Example 1: Probablistic Model . . . . . . . . . . Example 1: Analysis . . . . . . . . . . . . . . . . . . Example 2: Random Permutation of an Array Example 2: Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 3 4 5 6 7 Maximum(A) max A[1] for i 2 to length(A) do if max < A[i] then max A[i] return max Problem: How many assignments to max? Best-case: 1 (When does this happen?) Worst-case: n (When does this happen?) Average-case: (n + 1)/2 is incorrect
    CS 5633 Analysis of Algorithms Chapter 5: Slide 3

    Example 1: Probablistic Model


    Assume A has n distinct numbers. (What is the eect of duplicates?) Assume each permutation of the numbers is equally likely. (How can randomization guarantee this?) How many permutations are there? What is the probability of the best case? What is the probability of the worst case?
    CS 5633 Analysis of Algorithms Chapter 5: Slide 4

    Example 1: Analysis
    On iteration i, max is assigned a value i A[i] is the maximum of the rst i numbers. Probability that A[i] is the maximum of the rst i numbers = 1/i Probability of assignment = 1/i, cost = 1 Prob. of no assignment = (i 1)/i, cost = 0 On iteration i, the expected cost is: (1/i)(1) + ((i 1)/i)(0) = 1/i Over the initial assignment and n 1 iterations, the expected cost is: n 1 which is between ln n and 1 + ln n i=1 i
    CS 5633 Analysis of Algorithms Chapter 5: Slide 5

    Example 2: Random Permutation of an Array


    Randomize-In-Place(A) n length(A) for i 2 to n do swap A[i] A[Random(1, i)] Random(a, b) returns an integer r, a r b. r is equally likely to be any integer between a and b
    CS 5633 Analysis of Algorithms Chapter 5: Slide 6

    Example 2: Analysis
    Loop invariant: Before iteration i, A[1] through A[i 1] is a random permutation of the rst i 1 values. For any permutation of the rst i values, there is exactly one way to permute the rst i 1 values, and then swap A[i] into the correct position. So after iteration i, the rst i values have been randomly permuted, making the loop invariant true the next iteration.
    CS 5633 Analysis of Algorithms Chapter 5: Slide 7

    You might also like