Module 3 Flashcards
It is a straightforward approach based on the problem’s statement and concepts
Brute Force
What are the strengths of a brute force approach?
- Wildly applicable and simple
- Yields reasonable algorithms for some important problems
What are the weaknesses of a brute force approach?
- Rarely yields efficient algorithms
- Some brute-force algorithms are unacceptably slow
- Not as constructive as other design techniques
This type of algorithm sorts an array by repeatedly finding the minimum element from unsorted part and putting it at a subarray in the beginning.
Selection Sort
In this type of sorting algorithm, the minimum element from the unsorted subarray is picked and moved to the sorted subarray in every iteration.
Selection Sort
This type of algorithm compares a given pattern with all substrings of a given text.
Brute-Force String Matching
in this type of algorithm, comparisons between substring and pattern proceed character by character unless a mismatch is found.
Brute-Force String Matching
In this type of algorithm, whenever a mismatch is found, comparisons are dropped and the next substring can be selected immediately.
Brute-Force String Matching
It is a brute force solution to a problem involving search for an element with a special property.
Exhaustive Search
This consists of a salesman and a set of cities. The salesman has to visit each one of the cities starting from a certain one and returning to the same city.
Travelling Salesman Problem
This problem, given a set of items with a weight and a value, determines the items to include when picked so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Knapsack Problem
Who named the “Knapsack Problem”?
Tobias Dantzig
