Send the link below via email or IMCopy
Present to your audienceStart remote presentation
- Invited audience members will follow you as you navigate and present
- People invited to a presentation do not need a Prezi account
- This link expires 10 minutes after you close the presentation
- A maximum of 30 users can follow your presentation
- Learn more about this feature in our knowledge base article
Comparative Study of Brute-force Approach and Divide & Conquer Approach
Transcript of Comparative Study of Brute-force Approach and Divide & Conquer Approach
Divide & Conquer Approach Description of the algorithm Example
Recursive Binary Search Comparison of Brute-force Approach
And Divide & Conquer Approach Description of the problem Example
Selection sort 2. Divide & Conquer Approach Description of the algorithm Introduction Description of the problem Brute-Force Approach Brute force algorithm is a step-by-step recipe for solving a problem so it’s consider as a straightforward approach usually based on the problem's statement . Brute force is a straightforward approach to problem solving.
usually directly based on the problem’s statement and definitions of the concepts involved.
The brute-force approach should not be overlooked as an important algorithm design strategy.
Unlike some of the other strategies, brute force is applicable to a very wide variety of problems.
For some important problems (e.g., sorting, searching, string matching), the brute-force approach yields reasonable algorithms of at least some practical value with no limitation on instance size.
brute-force algorithm can still be useful for solving small-size instances of a problem.
A brute-force algorithm can serve an important theoretical or educational purpose. A brute-force algorithm solves a problem in the most simple, direct or obvious way. As a result, such an algorithm can end up doing far more work to solve a given problem than a more clever or sophisticated algorithm might do. On the other hand, a brute-force algorithm is often easier to implement than a more sophisticated one and, because of this simplicity, sometimes it can be more efficient.To solve a problem using the brute force technique, you just need to use facts derived from the problem statement without making an effort to make the algorithm smart. Scan the array to find its smallest element and swap it with the first element.
Then, starting with the second element, scan the elements to the right of it to find the smallest among them and swap it with the second elements.
Find the smallest element in A[i..n-1] and swap it with A[i]. Divide-and-conquer is a top-down technique for designing algorithms that consists of dividing the problem into smaller subproblems hoping that the solutions of the subproblems are easier to find and then composing the partial solutions into the solution of the original problem. Divide and conquer is a powerful tool for solving conceptually difficult problems, such as the classic Tower of Hanoi puzzle: all it requires is a way of breaking the problem into sub-problems, of solving the trivial cases and of combining sub-problems to the original problem. Divide problem into several smaller subproblems
normally, the sub-problems are similar to the original
Conquer the sub-problems by solving them recursively
Base case: solve small enough problems by brute force
Combine the solutions to get a solution to the sub-problems
finally a solution to the original problem. -Divide and conquer is a powerful tool for solving conceptually difficult problems, faster than brute-force algorithm because divide and conquer works by splitting up the original problem into smaller subproblems and then solves the smaller subproblems, these solutions reduce the total amount of work to do with respect to solving the original problem so yields Algorithm efficiency and Parallelism. But Brute force implies using the definition to solve the problem in a straightforward manner it is usually very slow . for a problem, if you can divide it into two sub-problems with the same pattern as the original one, and the time complexity to merge the results of the two sub-problems into the final result is somehow small, then it's faster than solve the original complete problem by brute-force.For example, the natural brute-force algorithm for finding the closest pair among n points in the plane would simply measure all Θ(n^2) distances, for a (polynomial) running time of Θ(n^2). Using divide-and-conquer, we will time to O(n log n). On the other hand, the ability to understand and design Divide and conquer algorithms is a skill that takes time to master Fast algorithms dramatically decrease run time for certain tasks. Designing them offers not only the promise of better performance but also a better understanding of the problems underlying all computational tasks.This report object is to design and analysis of modern algorithms, comparing efficiencies, advance designing techniques. In this report algorithm will be analyses using real world examples. It will includes: Brute Force, Divide and Conquer approach. Aisha Al Thunayan
Mshael Al Naim
Latifah Al Naim
Fatimah Al Turkey
Sarah Al Thuwaiqib Thank you Conclusion
Usually a given problem can be solved using various approaches however it is not wise to settle for the first that comes to mind. More often than not, some approaches result in much more efficient solutions than others.The basic question here is: How to choose the approach? First, by understanding the problem, and second, by knowing various problems and how they are solved using different approaches. Strongly recommended reading to learn more about how to design algorithms
-Brute force algorithms is used when the simplicity of implementation is more important than speed, usually the easiest to implement, brute force is applicable to a very wide variety of problems, yields reasonable algorithms, but the disadvantage of solving a problem and can be applied only to problems where input size is small otherwise will be not efficient, and require a huge number of steps , its cost is proportional to the number of candidate solutions - which in many practical problems tends to grow very quickly as the size of the problem increases