CST 370 - Week 3

 Hey everyone!

This week was packed with foundational concepts in computer science and algorithm design. From string matching to exhaustive search strategies and graph traversal techniques, I gained a clearer understanding of how various algorithms work under the hood and how they can be applied to solve complex problems. Here's a breakdown of what I learned:

I started the week exploring Brute Force String Matching, one of the simplest ways to find a pattern within a larger text. The method checks for a match by comparing the pattern to every possible position in the text. While it's not the most efficient, it’s a great way to understand the basics of string comparison and sets the stage for more advanced algorithms. The video walkthrough helped solidify how this method operates step-by-step.

I then moved on to Exhaustive Search strategies, which involve exploring all possible solutions to find the best one. Three classic problems were covered:

  • TSP (Travelling Salesman Problem): I learned how brute-force methods enumerate all possible paths to find the shortest route—a good example of combinatorial explosion.

  • Knapsack Problem: Showed how all combinations of items are considered to maximize value without exceeding weight.

  • Assignment Problem: Illustrated how each task-person pair is evaluated to find the optimal assignment.

The corresponding textbook readings (pages 115–120) gave a more formal explanation, reinforcing my understanding of the trade-offs between accuracy and efficiency.

Next, I explored DFS, a graph traversal technique that dives deep into each branch before backtracking. It was fascinating to see how it can be used in solving puzzles (like the Fake Coin problem) and pathfinding. The videos and the exercises really helped me grasp the recursive nature of DFS and its time efficiency implications.

In contrast to DFS, BFS explores all neighbors at one level before moving to the next. I learned how BFS can be used for shortest path problems in unweighted graphs. The BFS exercises provided hands-on practice and made the abstract idea much more tangible.

Toward the end of the week, I delved into Divide and Conquer, a paradigm that breaks a problem into smaller sub-problems, solves them independently, and combines their solutions. The Master Theorem was a bit challenging at first, but the video explanation and exercises helped me understand how it’s used to analyze time complexity.

The Fake Coin and Finger Count puzzles were fun and thought-provoking. They challenged me to apply algorithmic logic creatively, reinforcing the concepts from lectures.

This week was intense but incredibly rewarding. I now better appreciate the balance between algorithm simplicity and computational efficiency, and I’m beginning to recognize patterns in problem-solving strategies. Each topic built on the last, showing how foundational algorithms interconnect and support more complex logic in computing.

Looking forward to next week’s challenges!

Comments

Post a Comment

Popular posts from this blog

CST 370 - Week 1

 Hey everyone, This week, we learned several important topics that form the foundation of computer science and programming. We started with GitHub and practiced using manual commands like git init, git add, git commit, and git push to manage our code. This helped us understand version control and how to keep track of changes when working on projects, especially when collaborating with others. We were also introduced to algorithms and learned what they are—step-by-step methods for solving problems. One example we focused on was Euclid’s Algorithm for finding the greatest common divisor (GCD) of two numbers. It uses a simple but powerful idea: repeatedly replace the numbers with GCD(b, a % b) until the second number becomes zero. We also practiced writing pseudocode, which helped us plan out algorithms in plain language before coding. We also had a homework assignment to help us further understand GitHub commands. Later in the week, we learned about graphs, both weighted and unweight...
Read more

CST 370 - Week 5

 Hey everyone! This week, I explored several important algorithm design techniques and deepened my understanding of how they are applied in solving complex problems efficiently. One of the key highlights was learning about Quick Sort , a widely used sorting algorithm that relies on the Divide-and-Conquer strategy. I now understand how Quick Sort works by dividing the array into smaller parts around a pivot, sorting those parts recursively, and then combining the results. I also learned about its efficiency and how its performance depends on the choice of the pivot. I also studied Binary Tree traversal methods, such as inorder, preorder, and postorder, and how each serves a specific purpose when working with hierarchical data. Alongside traversal, I learned how to calculate the height of a binary tree , which is a foundational concept for evaluating the balance and efficiency of tree-based data structures. I even added my insights on the class Discord group, explaining an easy calc...
Read more

CST 370 - Week 4

 Hey everyone! This week in class, I focused on two main things: learning about Merge Sort and reviewing for the upcoming midterm . We covered Merge Sort in detail, and it really helped me understand how divide-and-conquer algorithms work. I learned that Merge Sort breaks down an array into smaller parts, sorts each part, and then merges them back together in a sorted order. What stood out to me is how efficient it is, especially for large datasets, with a time complexity of O(n log n) . I found the recursive nature of the algorithm interesting, and practicing it helped me see how smaller problems can be solved independently and then combined to solve the larger problem. Aside from learning new material, a big part of this week was focused on reviewing for the midterm . I went over topics from previous weeks like brute-force algorithms, string matching, and graph traversal methods (DFS and BFS). I also spent time practicing problems and using flashcards to reinforce key concepts....
Read more