CST 370 Week 3

 

WELCOME TO WEEK 3

Learning Journal - CST 370 

This week, we learned a lot. We started with Brute-Force String Matching, an algorithm that aligns the pattern against the first characters of the text and begins to match pairs of characters from left to right. It continues this process until there is either a match or, in the worst case, the pattern is not found in the text at all. The best case occurs when the first characters in the text immediately match the pattern.

Next, we learned about Exhaustive Search and its application to three important problems. Exhaustive Search is simply a brute-force approach to combinatorial problems such as permutations, combinations, and subsets of a given set. The first problem we covered was the Traveling Salesman Problem, which involves finding the shortest path through a set of cities (visiting each city exactly once) and returning to the starting city. It is also described as the problem of finding the shortest Hamiltonian cycle. The other problems discussed were the Knapsack Problem and the Assignment Problem.

We then moved on to Depth-First Search (DFS) and Breadth-First Search (BFS). We learned the differences between the two: DFS uses a stack, while BFS uses a queue. The algorithms differ in their approach, and their traversal graphs are represented differently. 

Finally, we touched on the topic of Divide-and-Conquer. This is a general algorithm design technique in which a problem is divided into smaller subproblems of the same type, solved recursively until they are small enough, and then combined to produce the final solution. To determine time efficiency for such algorithms, instead of using backward substitution, we use what is called the Master Theorem, which makes it much easier to calculate time efficiency. Based on the values of $a$, $b$, and $d$, one can determine the time efficiency by matching the problem to a specific case.

Besides learning a lot of new material, I felt this week was certainly harder than the previous two. I can see that we are diving deeper into the material, and with our midterm coming up this weekend, I feel quite anxious since it is closed-book. I tend to refer to my lectures when working on the exercises provided, so this will be a challenge. However, it’s good to know we can create cheat sheets, and I already have an idea of what to include. I also feel a bit more confident knowing we will meet on Thursday for a midterm review. That will definitely help calm my nerves.