CST370 - Module 3

What did I learn in the third week of CST370? 

This week we expanded on algorithm design through search strategies DFS and BFS. The module does begin though with the prior week's brute-force method, providing a clear baseline in starting off with brute-force string matching and exhaustive search, which reinforced what we learned previously on the inefficient but reliable way in solving problems. Furthermore, string matching simply checks every possible alignment, while the exhaustive search extends this to complex problems (i.e. Traveling Salesman), through a poorly scaled yet helpful way in understanding the systematic exploration of all possibilities within a given problem.

A majority of the material this time went over graph-search algorithms, with Depth-First Search (DFS) and Breadth-First Search (BFS). Basically, DFS explores the vertices as far as it can go before hitting a dead end and backtracking, while BFS explores all possible routes before taking the next step, assigning child and parent vertices that create a tree like structure. Therefore, DFS is more linear in searching, while BFS is more efficient in getting the shortest path in unweighted graphs. In the end, there are cons and pros to both search algorithms and it is determined by time-efficiency, analyzation, tracking, pathfinding, and cycle detection.

The final topic of the week introduced the divide-and-conquer algorithm design, showcasing how one can break down a problem to smaller subproblems and recursively solve them by combining the results, leading to highly efficient algorithms. This was honestly my first time being introduced to an algorithm that divides the problem to centralized subcategories through the master theorem, which are then structured in such a way that one can recursively resolve them without relying on substitution or recursion trees. In the end, this week was very comprehensive in introducing algorithmic strategies and approaches to resolving problems.