CST 370 - Week 3

This week's topics covered brute force string matching, depth search algorithm, breadth first algorithm, and an introduction to the divide and conquer algorithm design. Brute force, also known as exhaustive search, is a method under which all possible combinations can be checked (in the very worst case). For example, when trying to find a substring within a string, each position is checked until the correct match it found. Although it was the most simple method covered this week, generally speaking it is inefficient unless the dataset happens to be small. BFS (Breadth First Search) explores node by level, starting at the root, using a queue data structure. Depth First Search (DFS) is implemented by going down a branch and then backtracking. It uses a stack and can be implemented with recursion as shown in our recent homework. This was probably the most difficult method covered in class this week.