CST 370 - Week 7

 Hey everyone,

This week’s learning journey took me through several important algorithmic techniques and problem-solving strategies, expanding both my theoretical knowledge and my practical skills.

I began with Non-Comparison Sorting, where I explored Counting Sort and Radix Sort. Unlike traditional comparison-based methods like Merge Sort or Quick Sort, these algorithms leverage properties of the input data to achieve better-than-O(n log n) performance in certain cases. Counting Sort uses frequency counting to sort integers efficiently, while Radix Sort applies a digit-by-digit sorting approach (often using Counting Sort as a subroutine), making it especially useful for fixed-length integers or strings. The visualizations helped me understand how these algorithms maintain stability and avoid element comparisons altogether.

Next, I dove into Dynamic Programming (DP). The key takeaway was that DP is all about solving complex problems by breaking them into overlapping subproblems, storing solutions to avoid redundant work. I practiced with the Coin-Collecting problem, which reinforced the idea of building solutions from smaller optimal sub-solutions, and the Coin-Row problem, which highlighted how DP applies to optimization tasks with constraints (e.g., not taking adjacent coins). The concept of a “table” or array to store intermediate results became very clear during these exercises.

From there, I moved into graph algorithms. I learned Warshall’s Algorithm, which computes the transitive closure of a graph by progressively checking whether paths exist through intermediate vertices, and Floyd’s Algorithm, which finds the shortest paths between all pairs of vertices by iteratively improving distance estimates. Both reinforced the power of systematic, table-based iterative updates.

Finally, I studied the Greedy Technique through Prim’s Algorithm for finding a Minimum Spanning Tree. This was a great contrast to DP: instead of storing and reusing solutions, greedy algorithms build the solution step-by-step, always making the locally optimal choice in the hope it leads to a globally optimal one. Prim’s method showed how simple decisions (adding the cheapest available edge) can still yield optimal solutions for certain problems.

Discussion Tip:
I had even shared a discussion tip on the class forum on Discord:
" Hey everyone, I just wanted to share one tip that has helped me in this week's homework as well as studying for the final is that when learning new algorithms, try to connect them to problems we’ve already solved in a different way. For example, after studying Floyd’s Algorithm, I tried to compare it to running Dijkstra’s Algorithm from every vertex. This not only deepens understanding but also highlights why certain algorithms are preferred for specific scenarios."

Overall, this week helped me appreciate how different algorithmic strategies—non-comparison sorting, dynamic programming, greedy methods—are suited to different types of problems. Each approach offers its own balance of efficiency, complexity, and problem-solving style.

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