CST370 Module Three

 

CST370 Module Three

String Matching, Exhaustive Search, Depth First Search, Breadth First Search and the Divide and Conquer Algorithm

What I learned this week:

This week we covered various algorithms, including several brute-force methods and problems. One of which was Brute Force String Matching which looked to be similar to a fixed-sliding window problem. We also covered the Traveling Salesman Problem and the Assignment, both of which involve combinatorics. The Knapsack problem was unique and one of the first to study in the course that involves O(2^n) time complexity or exponential time. In order to count the number of plausible subsets you have to take 2^n from which, you must find the sum of either weight or value in order to determine the highest valued combination of key items. 

We also went over Depth First Search and Breadth First Search. The two types have many similarities but also unique differences. When it comes to DFS, it primarily uses the form of a stack, in order to keep track of previously visited nodes. where as BFS typically use queues. These two types of data structures make a distinguishing difference where as DFS uses LIFO for order, where as BFS uses queue and FIFO for Order.

We also went over Divide and Conquer and it's relation to recurrence and the Master Theorem.