Scribd Logo
Upload

Welcome to Scribd!

  • 53 views

    Brute Force: The Design and Analysis of Algorithms

    Uploaded by

    Alex Markle
    This document discusses brute force algorithms. It begins by defining brute force as a straightforward approach to solve problems directly from their definitions. It then provides examples of brute force search, sorting, string matching, and solving the closest pair and convex hull problems in O(n^2) or O(n^3) time. The document concludes by stating that brute force has wide applicability but rarely yields efficient algorithms and is not as constructive as other design techniques.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd

    Brute Force: The Design and Analysis of Algorithms

    Uploaded by

    Alex Markle
    53 views12 pages
    This document discusses brute force algorithms. It begins by defining brute force as a straightforward approach to solve problems directly from their definitions. It then provides examples of brute force search, sorting, string matching, and solving the closest pair and convex hull problems in O(n^2) or O(n^3) time. The document concludes by stating that brute force has wide applicability but rarely yields efficient algorithms and is not as constructive as other design techniques.

    Original Title

    4550800

    Copyright

    © © All Rights Reserved

    Available Formats

    PPT, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document discusses brute force algorithms. It begins by defining brute force as a straightforward approach to solve problems directly from their definitions. It then provides examples of brute force search, sorting, string matching, and solving the closest pair and convex hull problems in O(n^2) or O(n^3) time. The document concludes by stating that brute force has wide applicability but rarely yields efficient algorithms and is not as constructive as other design techniques.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    53 views12 pages

    Brute Force: The Design and Analysis of Algorithms

    Uploaded by

    Alex Markle
    This document discusses brute force algorithms. It begins by defining brute force as a straightforward approach to solve problems directly from their definitions. It then provides examples of brute force search, sorting, string matching, and solving the closest pair and convex hull problems in O(n^2) or O(n^3) time. The document concludes by stating that brute force has wide applicability but rarely yields efficient algorithms and is not as constructive as other design techniques.

    Copyright:

    © All Rights Reserved
    Download as PPT, PDF, TXT or read online from Scribd
    Download as ppt, pdf, or txt
    of 12

    The Design and Analysis of Algorithms

    Chapter 3: Brute Force


    Chapter 3. Brute Force Algorithms

     Basic Idea
     Brute Force Search and Sort
     Brute Force String Matching
     Closest Pair and Convex Hull Problems
     Exhaustive Search
     Conclusion

    2
    Basic Idea
     A straightforward approach to solve a
    problem based on the problem’s
    statement and definitions of the concepts
    involved.

     Example
    Computing an based on the definition of exponentiation:
    an = a* a* a* …. * a

    (a > 0, n a nonnegative integer)

    3
    Brute Force Search and Sort
     Sequential Search O(n)
     Selection Sort O(n2)
     Bubble Sort O(n2)

    4
    Brute Force String Matching
    Pattern: program
    Comparisons:
    Text:
    (n*m) in the worst
    possible case
    Write a program.
    (n+m)  (n) in the
    program
    average case.
    program
    …
    program

    5
    Closest Pair Problem
    Find the two closest points in a set of
    n points in k-dimensional space.
    Algorithm ClosestPairPoints (P)
    dmin ← ∞
    for i ← 1 to n-1 do
    for j ← i + 1 to n do
    d ← sqrt ((xi – xj) 2 + (yi – yj)2)
    if d < dmin
    (n2) dmin ← d

    6
    Convex Hull Problem
     Convex set: For any two points P and Q in the
    set, the entire line segment with the end points
    at P and Q belongs to the set
     Convex hull of a set S of points is the smallest
    convex set containing S

    The convex hull of any set S of n > 2 points is a


    convex polygon with the vertexes at some of
    the points of S.
    7
    Convex Hull Problem

    Algorithm:
    for each of n(n-1)/2 pairs of distinct points
    for each of the other n – 2 points
    find the sign of ax + by – c

    The time efficiency of this algorithm is O(n3).

    8
    Exhaustive Search
    State-space search
    Given an initial state,
    a goal state, and
    a set of operations,
    find a sequence of operations that transforms the
    initial state to the goal state.

    The solution process can be represented as a tree

    9
    Exhaustive Search
    Combinatorial problems

     Traveling Salesman – permutations  ((N-1)!)

     Knapsack – subsets  (2N)

     Assignment problem – permutations


     (N!)

    10
    Conclusion - Strengths

     Wide applicability, simplicity


     Reasonable algorithms for some important
    problems such as searching, string matching,
    and matrix multiplication
     Standard algorithms for simple computational
    tasks such as sum and product of n numbers,
    and finding maximum or minimum in a list

    11
    Conclusion - Weaknesses
     Brute Force approach rarely yields
    efficient algorithms
     Some brute force algorithms are
    unacceptably slow
     Brute Force approach is neither as
    constructive nor creative as some other
    design techniques

    12

    You might also like