CST370 - Week 3

 

CST370-30_2252: Design & Analysis of Algorithms – Week 3

This is the third week; we continue reviewing various problem-solving techniques. The last module introduced brute force as a direct “just do it” solving the problem. The example of Brute-Force String Matching analysis is based on the text of the string and the pattern of comparison. In a best-case scenario, a direct match is found at the start of the string. The algorithm is simple as we compare the first character of the pattern for a match or shift the pattern one character to the right if there is no match. The worst case requires comparing all the pattern characters for every shift m * (n – m +1) where m characters are in the pattern and n are in the text.

The following exhaustive search-combinatorial problems are new to me, except for the optima route. We reviewed three brute-force approaches with different strategies and time complexity. First is the traveling salesman problem or TSP; it is represented by a directed weighted graph. The idea of TSP is to find the optimal route between vertices among all of the possibilities. The second problem is the Knapsack, which searches for the maximum value of a subset of items with total weight that does not exceed a certain capacity. The subsets generated are for n elements to return Ω (for its algorithm analysis. The third is the assignment problem that assigns one job from n jobs to each person in n persons with the minimum cost possible.

Further, the module introduces depth-first search (DFS) and breadth-first search (BFS) as graph problems. These are fascinating algorithms and powerful graph traversal. However, I still need to do more research to understand their practical applications. There are a few helpful exercises in the textbook to practice the DFS traversal and represent solutions in tree edges. The breadth-first search BFS traversal is different, and it uses a queue instead of the stack used in the DFS. In this case, all adjacent vertices to the starting vertex must be visited first.

The module ends with an introduction to the divide-and-conquer algorithm design. The idea behind this technique is to break down the main problem into small sub-problems until they are small enough to solve directly. The subproblems are solved recursively, then added, and so on until the entire divided problem is resolved. The time efficiency of the divide-and-conquer algorithm is calculated using the Master Theorem.