CST 370: Learning Journal Week 3

This week we covered brute force and exhaustive search, depth-first search (DFS), breadth-first search (BFS), and an introduction to divide-and-conquer algorithms. 

Brute force string matching and exhaustive search, which emphasize solving problems by checking all possible solutions. Brute force string matching works by aligning a pattern with a text and comparing characters one by one until a match is found or all possibilities are exhausted. It is often inefficient for large inputs. The key concept was that brute force guarantees correctness but does not scale well, making it impractical for complex or large datasets.

Depth-First Search (DFS), an algorithm used primarily for traversing graphs and trees. DFS works by exploring as far as possible along one path before backtracking. This method is useful for tasks like path discovery, cycle detection, and connectivity analysis. One important takeaway was that DFS uses a stack-based approach, which affects memory usage and traversal order. 

BFS uses a queue and is especially useful when the shortest path (in terms of number of edges) is needed. Algorithm choice matters depending on the goal—while DFS may go deep quickly, BFS ensures the earliest solution in terms of distance, which is crucial in routing and networking problems.

Divide-and-conquer algorithms work by breaking a problem into smaller subproblems, solving them independently, and then combining the results. Understanding how problem structure and recursion can dramatically improve efficiency compared to brute force methods.