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 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.