Week 66: CST370 - Design and Analysis of Algorithms

WK07: Weekly Reflection

This week's module focused on dynamic programming, Warshall's algorithm, Floyd's algorithm, greedy techniques, and Prim's algorithm. These topics helped me understand ways to solve optimization and graph problems.

One topic that stood out was dynamic programming. I learned that it works by breaking a problem into smaller overlapping subproblems and reusing previously calculated results instead of solving the same problem again. The Coin-Row problem helped me understand this idea because the goal is to choose coins with the greatest total value without selecting adjacent coins. I also practiced the Coin-Collecting problem, where values are calculated step by step across a grid to find the maximum number of coins that can be collected.

Another important topic was Warshall's algorithm. I learned that it is used to find the transitive closure of a directed graph. It shows whether a path exists from one vertex to another, even when there is no direct edge between them. The exercises helped me understand how the reachability matrix changes as more intermediate vertices are allowed. The Missionaries and Cannibals puzzle also showed how graph states and transitions can be used to represent and solve a problem.

Floyd's algorithm was similar to Warshall's algorithm, but instead of checking reachability, it finds the shortest paths between all pairs of vertices in a weighted graph. I learned how the distance matrix is updated by checking whether traveling through an intermediate vertex creates a shorter path.

The final topic was the greedy technique and Prim's algorithm. I learned that a greedy algorithm makes the best available choice at each step. Prim's algorithm applies this idea to find a Minimum Spanning Tree by repeatedly selecting the lowest-cost edge that connects a visited vertex to an unvisited vertex.

Overall, this week helped me see how different algorithmic strategies are suited to different problems. Dynamic programming reuses solutions to smaller problems, Warshall's algorithm finds reachability, Floyd's algorithm finds shortest paths, and Prim's algorithm builds a minimum-cost spanning tree. My main takeaway is that understanding the structure of a problem helps determine which algorithm is the most appropriate and efficient.

Comments

Post a Comment

Popular posts from this blog

Week 20: CST 363 - Introduction to Database Systems

   WK04:  Midpoint Reflections I'm not new to databases and have some practical experience with SQL, but this course gave me the theoretical backbone for concepts I've used pragmatically. I connected everyday tasks - designing tables, choosing keys, writing joins, and skimming plans - to the relational model and formal normalization. Seeing why clustered vs. heap layouts affect access, how B-tree indexes support equality/range predicates, and where optimizers derive their strategies clarified earlier "rules of thumb." Overall, I gained vocabulary and structure to justify design choices. Brief Summary of 5 Things Learned I strengthened the relational model: entities/attributes, candidate vs. primary keys, and why foreign keys enforce meaning across tables. I practiced expressive SQL beyond basics - joins, subqueries, and aggregates - while reading execution plans to understand scans, seeks, and join algorithms. I deepened constraints and referential integrity to preven...
Read more

Week 17: CST 363 - Introduction to Database Systems

 WK01: Starting CST363 – Introduction to Databases This week I officially started a new course: CST363 – Introduction to Database Systems . The class looks like a solid mix of theory and practice. We'll design relational schemas, practice SQL queries, connect to databases programmatically, and even touch on NoSQL concepts like MongoDB. The syllabus makes it clear that this isn't just about running commands - it's about understanding the underlying algorithms, data structures, and principles that power modern database systems. That excites me, since databases are everywhere, from apps to analytics pipelines. Relational Databases vs. Spreadsheets At first glance, relational database tables and spreadsheets look the same - rows and columns full of data. But digging deeper, the differences are critical. Spreadsheets are flexible but mostly unstructured; you can mix data types freely, create ad hoc formulas, and manually tweak things. Databases, on the other hand, enforce stric...
Read more

Week 11: CST 338 - Software Design

  Week 3 Learning Journal – HW 1 Code Review This week was extremely busy. Between multiple programming assignments, studying for quizzes, and finishing up other coursework, I didn't get a single day off - not even Sunday. I worked through the entire weekend just to keep up. One of the last things I tackled was the code review assignment, not because it was difficult, but because it was worth fewer points compared to other assignments. Ironically, despite being worth less than half of another assignment, it took nearly the same amount of time. Reading, testing, and analyzing other students' code takes real focus - especially when you're trying to give meaningful feedback and not just check a box. But I'll be honest: even though it felt like extra work at first, the peer code review assignment turned out to be one of the most helpful parts of the week. Looking through other people's code - seeing what they did right, where they made mistakes, or how they handled logi...
Read more