What is brute force algorithm?

A strategy that is simple and uncomplicated, which is typically based directly on the statement of the problem and definitions of the ideas that are involved.

Mention pros and cons of brute force approach.

Pros:

• Wide applicability
• Simplicity
• Yields reasonable algorithms for some important problems

Cons:

• rarely yields efficient algorithms
• some brute-force algorithms are unacceptably slow and not as constructive as some other design techniques

What is an exhaustive search?

A solution to a problem involves searching for an element that has a specific property, typically among combinatorial objects such as permutations, combinations, or subsets of a set. This type of solution is considered to be a brute-force solution.

Give the general plan of exhaustive search.

Method:

• Generate a list of all potential solutions to the problem in a systematic manner
• Evaluate potential solutions one by one, disqualifying infeasible ones and, for an optimization problem, keeping track of the best one found so far
• When the search ends, announce the solution(s) found

Define of feasibility

If a viable set (of candidates) can be extended to generate not just a solution, but also the best possible solution to the problem, then this is said to be promising.

Define mergesort.

Mergesort sorts a given array A[0..n-1] by dividing it into two halves a[0..(n/2)-1] and A[n/2..n-1] sorting each of them recursively and then merging the two smaller sorted arrays into a single sorted one.

List the Steps in Merge Sort

• Divide Step: If given array A has zero or one element, return S; it is already sorted. Otherwise, divide A into two arrays, A1 and A2, each containing about half of the elements of A.
• Recursion Step: Recursively sort arrays A1 and A2.
• Conquer Step: Combine the elements back in A by merging the sorted arrays A1 and A2 into a sorted sequence

List out the Disadvantages of Divide and Conquer Algorithm

• Conceptual difficulty
• Recursion overhead
• Repeated subproblems

Define Quick Sort

It is not difficult to build a quick sort, it is an excellent “general purpose” sort, and it consumes relatively fewer resources while it is being executed. These are the three main reasons why the quick sort is the algorithm of choice in many circumstances.

List out the Advantages of Quick Sort

• It is in place since it uses only a small auxiliary stack.
• It requires only n log(n) time to sort n items.
• It has an extremely short inner loop
• This algorithm has been subjected to a thorough mathematical analysis, and a very precise statement can be made about performance issues.

List out the Disadvantages in Quick Sort

• It is recursive. Especially if recursion is not available, the implementation is extremely complicated.
• It requires quadratic (i.e., n²) time in the worst case.
• It is fragile i.e., a simple mistake in the implementation can go unnoticed and cause it to perform badly.