Brute Force Concepts

Define the "Brute Force" approach to problem-solving.

Brute force is a straightforward approach to solving a problem, usually directly based on the problem statement and definitions of the concepts involved. It can also be described by the phrase "Just do it!".

What are the general advantages and limitations of the Brute Force method in algorithm design?

The principal strengths of the brute-force approach are its wide applicability and simplicity. Unlike some other strategies, brute force is applicable to a very wide variety of problems. It seems to be the only general approach for which it is more difficult to point out problems it cannot tackle. Brute force algorithms are often the easiest to apply.

The principal weakness of the brute-force approach is the subpar efficiency of most brute-force algorithms. It is rarely a source of clever or efficient algorithms.

Write two key differences between the Brute Force and Divide-and-Conquer techniques of algorithm design.

One key difference lies in their fundamental approach:

• Brute force is a straightforward method that directly follows the problem statement and definitions, often exploring the problem domain exhaustively or checking possibilities one by one.

• Divide-and-conquer solves a problem by breaking it down into several smaller instances of the same problem, solving each instance recursively, and then combining the solutions to the smaller instances to obtain a solution to the original problem.

Another difference is in how they handle sub-problems:

• Brute force typically tackles the problem directly or by systematically generating and checking candidates.

• Divide-and-conquer solves smaller instances of the same problem. These sub-problems are usually independent.

When might a Brute Force approach be considered a practical or reasonable choice for solving a problem?

A brute-force algorithm can be a practical or reasonable choice in several situations:

• Even if too inefficient in general, a brute-force algorithm can still be useful for solving small-size instances of a problem.

• For some important problems like sorting, searching, matrix multiplication, and string matching, the brute-force approach yields reasonable algorithms of at least some practical value with no limitation on instance size.

• A brute-force algorithm can serve an important theoretical or educational purpose as a yardstick with which to judge more efficient alternatives for solving a problem.

• Its wide applicability and simplicity also make it a default approach when more sophisticated methods are not immediately obvious or necessary.

• A first application of the brute-force approach often results in an algorithm that can be improved with a modest amount of effort.

• When the expense of designing a more efficient algorithm may be unjustifiable if only a few instances of a problem need to be solved and a brute-force algorithm can solve those instances with acceptable speed.

Selection Sort

Describe the Selection Sort algorithm.

Selection sort is a brute-force approach to the sorting problem. It works by repeatedly finding the smallest element from the unsorted portion of the list and exchanging it with the element at the current position.

Specifically, the algorithm starts by scanning the entire list to find its smallest element and swaps it with the first element.

Then, it scans the list starting from the second element to find the smallest among the remaining elements and swaps it with the second element.

This process continues, where on the i_th pass (from 0 to n - 2), the algorithm searches for the smallest item among the last n - i elements and swaps it with the element at position i.

After n - 1 passes, the list is sorted.

Write a clear algorithm or pseudocode for Selection Sort.

ALGORITHM SelectionSort(A[0..n − 1])
//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 nondecreasing order

for i ← 0 to n − 2 do
	min ← i
	for j ← i + 1 to n − 1 do
		if A[j ] < A[min]
			min ← j
	swap A[i] and A[min]

Analyze the time complexity of the Selection Sort algorithm.

The analysis of selection sort is straightforward.

• The input size is the number of elements, n.

• The basic operation is the key comparison A[j] < A[min].

• The number of times this basic operation is executed depends only on the array size n. Thus, there is no need to distinguish between worst-case, average-case, and best-case efficiency for the number of comparisons.

• The number of comparisons is given by the sum:

• C(n) = ∑_i=0__n-2_ ∑_j=i+1__n-1_ 1

• This sum evaluates to ∑_i=0__n-2_ (n - 1 - i), which is the sum of decreasing integers from n - 1 down to 1.

• The result of this sum is (n - 1)n / 2.

• Therefore, selection sort is a Θ(n2) algorithm for key comparisons on all inputs.

• Note that the number of key swaps is n - 1, which is in Θ(n). This property positively distinguishes it from many other sorting algorithms.

Is Selection Sort a stable sorting algorithm? Explain your answer.

No — Selection Sort is not stable.

A sorting algorithm is stable if it preserves the relative order of equal elements.
That is, if two equal elements appear at positions i and j in the input where i < j, they must appear in the same order in the output.

Selection Sort can break this rule because it swaps the current element with the minimum element found in the unsorted portion. This swap is not restricted to adjacent elements, so an equal element appearing later can be moved before another equal element that appeared earlier.

Example: Consider the list:

[A1, B, A2]    // A1 and A2 have equal values, but are distinct items

• The minimum in the whole array is A1 (already in position 0), so no change.

• Now look at the subarray [B, A2]. The minimum is A2, which swaps with B → [A1, A2, B] (order preserved).

But consider:

[A2, B, A1]

• The minimum is A1, which swaps with A2 → [A1, B, A2].
  Here, A1 (originally after A2) has moved before A2, reversing their original order.

This shows that Selection Sort is not stable, because its swapping step can reorder equal elements.

Trace the execution of the Selection Sort algorithm on the following lists of numbers/characters:

Initial list: [81, 43, 66, 87, 21, 34, 15], (n=7)

• i = 0: Find minimum in . Minimum is 15 at index 6. Swap `A` and `A`. State:

• i = 1: Find minimum in . Minimum is 21 at index 4 (of original array, index 3 of sublist). Swap `A` and `A`. State:

• i = 2: Find minimum in . Minimum is 34 at index 5 (of original array, index 3 of sublist). Swap `A` and `A`. State:

• i = 3: Find minimum in . Minimum is 43 at index 4 (of original array, index 1 of sublist). Swap `A` and `A`. State:

• i = 4: Find minimum in . Minimum is 66 at index 5 (of original array, index 1 of sublist). Swap `A` and `A`. State:

• i = 5: Find minimum in . Minimum is 81 at index 6 (of original array, index 1 of sublist). Swap `A` and `A`. State:

• i = 6: Loop finishes as i goes up to n-2 (which is 5).

Sorted list: [15, 21, 34, 43, 66, 81, 87 ]

---

• [S, E, Q, U, E, N, T, I, A, L] (in alphabetical order) (n=10)

Initial list: [S, E, Q, U, E, N, T, I, A, L]

• i = 0: Min is 'A' at index 8. Swap A and A. State: [A, E, Q, U, E, N, T, I, S, L]

• i = 1: Min is 'E' at index 1. Swap A and A. State: [A, E, Q, U, E, N, T, I, S, L] (No change)

• i = 2: Min in [Q, U, E, N, T, I, S, L] is 'E' at index 4 (original index). Swap A and A. State: [A, E, E, U, Q, N, T, I, S, L]

• i = 3: Min in [U, Q, N, T, I, S, L] is 'I' at index 7 (original index). Swap A and A. State: [A, E, E, I, Q, N, T, U, S, L]

• i = 4: Min in [Q, N, T, U, S, L] is 'L' at index 9 (original index). Swap A and A. State: [A, E, E, I, L, N, T, U, S, Q]

• i = 5: Min in [N, T, U, S, Q] is 'N' at index 5 (original index). Swap A and A. State: [A, E, E, I, L, N, T, U, S, Q] (No change)

• i = 6: Min in [T, U, S, Q] is 'Q' at index 9 (original index). Swap A and A. State: [A, E, E, I, L, N, Q, U, S, T]

• i = 7: Min in [U, S, T] is 'S' at index 8 (original index). Swap A and A. State: [A, E, E, I, L, N, Q, S, U, T]

• i = 8: Min in [U, T] is 'T' at index 9 (original index). Swap A and A. State: [A, E, E, I, L, N, Q, S, T, U]

• i = 9: Loop finishes as i goes up to n-2 (which is 8).

Sorted list: [A, E, E, I, L, N, Q, S, T, U]