Week 3 covered a few brute force algorithms: sequential search, string matching, and the two graph traversal algorithms (DFS and BFS). We also started learning about divide-and-conquer algorithms, which we will study more in the coming weeks.
Searching and string matching
Sequential search is a common brute force technique. Basically, you just check every item until you find the one you’re looking for.
To find a substring in a string, we can use brute-force string matching. The main idea is that you check a pattern of m characters at each of the n − m + 1 possible positions, shifting one position to the right on a mismatch, until you find the complete substring or reach the the end of the window (in which case there is no match). Levitin’s textbook provides the following pseudocode:
The worst case is m(n − m + 1), or O(nm), because the inner loop runs m times for each of the n - m + 1 iterations of the outer loop.
Exhaustive search
Exhaustive search is brute force applied to combinatorial problems, like the traveling salesman problem (TSP). The main idea is that you generate every possible combination and then pick the best one. For TSP, this means generating every possible tour that visits each city exactly once and returns to the starting city, in order to calculate the total cost of each tour and choose the shortest one. Exhaustive search is guaranteed to find the optimal solution, but it becomes impractical for large inputs because the number of possible solutions grows extremely quickly.
DFS and BFS
Depth-first search (DFS) and breadth-first search (BFS) are two common graph traversal algorithms. DFS explores as far as possible along one path before backtracking and often uses recursion. BFS explores the graph level by level, visiting all neighboring vertices before moving farther away and is usually implemented with a queue. Both can be used to visit all reachable vertices, but they explore the graph in different orders.