Design and Analysis of Algorithms

I collect and make up this pseudocode from the book:

<<Introduction to the Design and Analysis of Algorithms_Second Edition>> _ Anany Levitin
Note that throughout the paper, we assume that inputs to algorithms fall within their specified ranges and hence require no verfication. When implementing algorithms as programs to be used in actual applications, you should provide such verfications.
About pseudocode: For the sake of simplicity, we omit declarations of variables and use indentation to show the scope of such statements as for, if and while. As you saw later, we use an arrow <- for the assignment operation and two slashes // for comments.　

Algorithm SelectionSort(A[..n-])

    // Sorts a given array by selection sort

    // Input: An array A[0..n-1] of orderable elements

    // Output: Array A[0..n-1] sorted in ascending order

    for i <-  to n- do

        min <- i

        for j <- i+ to n- do

            if A[j] < A[min]

                min <- j

        swap A[i] and A[min]

Algorithm BubbleSort(A[..n-])

    // Sorts a given array by bubble sort

    // Input: An array A[0..n-1] of orderable elements

    // Output: Array A[0..n-1] sorted in ascending order

    for i <-  to n- do

        for j <-  to n--i do

            if A[j+] < A[j]

                swap A[j] and A[j+]

Here is a pseudocode for the improved version of bubble sort:

Algorithm BetterBubbleSort(A[..n-])

    // The algorithm sorts array A[0..n-1] by improved bubble sort

    // Input: An array A[0..n-1] of orderable elements

    // Output: Array A[0..n-1] sorted in ascending order

    count <- n- // number of adjacent pairs to be compared

    sflag <- true // swap flag

    while sflage do

        sflage <- false

        for j <-  to count- do

            if A[j+] < A[j]

                swap A[j] and A[j+]

                sflag <- true

        count <- count-

 

Here is a pseudocode of teh most straightforward version:
Algorithm BruteForcePolynomialEvaluation(P[..n], x)

    // The algorithm computes the value of polynomial P at a given point x by the 
    // 　　　　"highest-to-lowest" brute-force algorithm

    // Input: Array P[0..n] of the coefficients of a polynomial of degree n, stored from the lowest 
    // 　　　　to the highest and a number x

    // Output: The value of the polynomial at the point x

    p <- 0.0

    for i <- n downto  do

        power <-

        for j <-  to i do

            power <- power*x

        p <- p + P[i]*power

    return p

We can count just the number of multiplications in the algorithm's inner-most loop to find the algorithm's efficiency class: M(n) = n(n+1)/2 = O(n^2)

The above algorithm is very inefficient: we recompute powers of x again and again as if there were no relationship among them. Thus, the obvious improvement is based on computing consecutive powers more efficiently:

Algorithm BetterBruteForcePolynomialEvaluation(P[..n-], x)

    // The algorithm computes the value of polynomial P at a given point x by the
    // 　　　　"lowest-to-highest term" algorithm

    // Input: Array P[0..n] of the coefficients of a polynomial of degree n, from the 
    // 　　　　lowest to the highest, and a number x

    // Output: The value of the polynomial at the point x

    p <- P[]; power <-

    for i <-  to n do

        power <- power*x

        p <- p + P[i]*power

    return p

The number of multiplications here is M(n) = 2n, in another word, we have a linear algorithm

Algorithm SequentialSearch2(A[..n], K)

    // Implements sequential search with a search key as a sentinel

    // Input: An array A of n elements and a search key K

    // Output: The index of the first element in A[0..n-1] whose value is equal

    //              to K or -1 if no such element if found

    A[n] <- K

    i <-

    while A[i] ≠ K do

        i <- i +

    if i < n return i

    else return -

Algorithm BruteForceStringMatch(T[..n-], P[..m-])

    // Implements brute-force string matching

    // Input: An array T[0..n-1] of n characters representing a text and

    //            an array P[0..m-1] of m characters representing a pattern

    // Output: The index of the first character in the text that starts a

    //             matching substring or -1 if the search is unsuccessful

    for i <-  to n-m do

        j <-

        while j < m and P[j] = T[i+j] do

            j <- j+

        if j = m return i

    return -

Algorithm BruteForceClosestPoints(P)

    // Finds two closest points in the plane by burte force

    // Input: A list P of n(n ≥ 2) points P₁ = (x₁, x₂),...,P_n = (x_n, y_n)

    // Output: Indices index1 and index2 of the closest pair of points

    dmin <- ∞

    for i <-  to n- do

        for j <- i+ to n do

            d <- sqrt((x_i-x_j) + (y_i-y_j)) // sqrt is the square root function. In fact, computing square roots can be avoided, the trick is to realize that we can simply ignore the square root function

            if d < dmin

                dmin <- d; index1 <- i; index2 <- j

    return index1, index2

Let x₁ < x₂ < ... < x_n be real numbers representing coordinates of n villages located along a straight road. A post office needs tobe built in one of these villages. Design an efficent algorithm to find the post offfice location minimizing  the maximum distance from a village to the post office.

Assuming that the points x₁, x₂, ... x_n are given in increasing order, the answer is the point xi that is the closest to m = (x₁ + x_n) / 2, the middle point between x₁ and x_n. (The middle point woule be the obvious solution if the post-post office didn't have tobe at one of the given locations.) Indeed, if we put the post office at any location x_i to the left of m, the longest distance froma village to the post office would be x_n - x_i; this distance is minimal for the rightmost among such points. If we put the post office at any location x_i to the right of m, the longest distance from a village to the post office would be x_i - x₁; this distance isminimal for the leftmost among such points.

Algorithm PostOffice(P)

    // Input: List P of n(n ≥ 2) point s x₁, x₂,..., x_n in increasing order

    // Output: Point x_i that minimizes max_(1≤j≤n)|x_j - x_i| among all x₁,x₂,...,x_n

    m <- (x₁+x_n) /

    i <-

    while x_i < m do

        i <- i+

    if x_i - x₁ < x_n - x_i-

        return x_ielse return x_i-

new words:

polynomial: 多项式    coefficient: 系数 inefficient: 低效的

sentinel: 哨兵 plane: 平面 coordinate: 坐标

village: 村庄 straight: 直; 直线

(END_XPJIANG)

巴特西

Design and Analysis of Algorithms_Brute Froce

最新文章

热门文章