CST370: Design and Analysis of Algorithms, Week 3
Week 3 This week we covered brute force and exhaustive search, depth-first search (DFS), breadth-first search (BFS), and divide and conquer. DFS and BFS were probably the easiest concepts for me to grasp this week. The way I keep them straight is that BFS tries to go as wide as possible, while DFS tries to go as deep as possible. Thinking about them that way made the difference between the two much easier for me to remember. We also covered brute force and exhaustive search with examples like string matching, the traveling salesman problem, knapsack, and assignment problems. Those were fairly straightforward conceptually because the basic idea is to try the possible options and then determine which one works or which one is best. The part I struggled with most was the Master Theorem. I understand that it is used with divide-and-conquer algorithms to help determine time efficiency, but I had a hard time conceptualizing how all of the pieces fit together. I was also reviewing that s...
