In class, we introduced the basic definitions of Big-O notation which forms the basis for the study of the complexity of algorithms. Today, we’ll use Big-O to understand an intuitive, yet frequently inefficient class of algorithms.

Problem: Brute-force

Many algorithms in computing can be classified as combinatorial algorithms. To develop a combinatorial problem for a problem, we must cast that problem as a search for an object of interest from among a finite set of possibilities. Thus, we can think of the algorithm as a search procedure that moves through the space of possibilities in as efficient of a manner as possible.

If there are a finite number of possibilities, then one simple class of combinatorial algorithms are brute-force algorithms where we ignore efficiency and simply try all possible possibilities in some systematic fashion. While seemingly inelegant, sometimes brute-force solutions are the more pragmatic approach—and sometimes even more efficient in real-world settings! However, in many other cases, it is precisely avoiding brute-force search that is the purpose of the algorithm we develop for a task at hand.

Each of the following situations describes a problem that can be recast as a combinatorial algorithm. For each situation:

• Describe what the finite set of possibilities are and the object of interest you are looking for.
• Give a combinatorial description of the number of possibilities that a brute force algorithm would search through.
• From the combinatorial description, give the (temporal) computational complexity in Big-O notation of the associated brute force algorithm for that problem.
• Finally, from the Big-O description you gave, state whether the brute force algorithm is an efficient solution to the problem.

Note that some of the situations described below come from our previous lab on graph problems

1. Finding the smallest element among \(n\) elements of an array.
2. Finding a path between points \(u\) and \(v\) in a simple graph \(G = (V, E)\).
3. Determining whether the \(n\) elements of an array are in sorted order.
4. Given a bipartite graph \(G = (V, E)\) with \(V_1, V_2 \subseteq V\) forming a partition of \(V\) and a matching \(M \subseteq E\), determining whether \(M\) is a perfect matching.
5. Given a bipartite graph \(G = (V, E)\) with \(V_1, V_2 \subseteq V\) forming a partition of \(V\) and a matching \(M \subseteq E\), determine whether \(G\) has a perfect matching.
6. Given a simple \(G = (V, E)\), determine whether \(G\) has a \(k\)-coloring.