CST370 - Week 3

This week, we learned about the Brute Force method to approaching problems. This method aims to solve the problem in the simplest way without giving consideration to time and memory. We saw examples of this method with string matching. Then, we learned about exhaustive search and applied this method to three famous problems: the traveling salesman problem, the knapsack problem, and the assignment problem. Next, we looked at the Depth-First Search (DFS) and Breadth-First Search (BFS), two approaches to tree traversal. DFS uses a stack and mark array, while BFS uses a queue and mark array. Lastly, we started the topic of divide and conquer. With this method, a problem is split into subproblems and their solutions are combined.

For the homework, we were assigned 3 programs. The first program was to check if a string is a palindrome using a recursive function. The next program read input graph data from the user and displayed the path and cost of the solution to the traveling salesman problem. The last program was supposed to implement the DFS algorithm, but I had trouble with it and not enough time to figure it out, so I handed it in not fully completed.