Posts

Week 7 Learning journal- CST370

-
This week I learned about non-comparison sorting, dynamic programming, graph algorithms, and the greedy technique. We started with Counting Sort and Radix Sort, which sort without comparing elements. Counting Sort uses frequency and distribution tables to place elements directly, running in O(n + k) time. Radix Sort applies Counting Sort digit by digit starting from the least significant digit, running in O(d(n + k)) time, which is often linear. This week focused on dynamic programming. I learned that the core idea is to solve overlapping subproblems once and store results in a table to avoid redundant work. We went through the Fibonacci sequence example, then the coin-row problem where you pick non-adjacent coins for maximum value, and the coin-collecting problem where a robot moves right or down on a grid to collect the most coins. I ended up implementing the coin-collecting problem for HW6-1 using the recurrence F(i,j) = max{F(i-1,j), F(i,j-1)} + c_ij, which helped me understand ho...
Post a Comment
Read more

Week 6 Learning journal- CST370

-
This week, I mainly learned about two major topics: Heaps and Hashing. I started by learning about the Max Heap, which is a really efficient way to implement a priority queue. It was interesting to see how a complete binary tree can be represented using a simple array with 1-based indexing. This trick makes navigating between parents and children (using i/2, 2*i, etc.) super fast without needing pointers. I also spent time understanding the core operations like insertion (where you add to the end and sift up) and deletion (swapping the root with the last element and sifting down). One key takeaway for me was realizing that building a heap from scratch can be done in O(N) time using a bottom-up approach, which is much better than the O(N \log N) approach of inserting elements one by one. The second part of the module focused on Hashing, which is all about fast data retrieval. I learned how hash functions map keys to table indices and why handling collisions is so important. The concept...
Post a Comment
Read more

Week 5 Learning journal- CST370

-
This week's module focused on the practical application of the Divide and Conquer strategy through Quicksort and the logic of dependency management using Topological Sorting. Quicksort is an efficient, in-place sorting algorithm, which means it sorts the input array without requiring significant additional storage. A key component of its performance is the partitioning process, where a pivot is selected to split the array into two subarrays. I learned that using a Median-of-Three pivot selection is a common technique to avoid the worst-case time complexity of O(n^2) that occurs when the input is already sorted. The study of graph algorithms introduced Topological Sorting specifically for Directed Acyclic Graphs (DAGs). Using Kahn's Algorithm, I explored how to order vertices linearly based on their in-degrees. This process involves identifying vertices with an in-degree of zero, adding them to a queue, and then updating the in-degrees of their neighbors as they are processed. T...
Post a Comment
Read more

Week 4 Learning Journal- CST370

-
This week focused on the core mechanics of algorithm design, specifically the differences between Divide and Conquer and Decrease and Conquer. One of the most important takeaways for me was breaking down QuickSort. While I knew it was a popular sorting method, I didn't fully appreciate how much the "pivot" choice matters. The fact that it's an in-place algorithm is a huge advantage over Merge Sort because it doesn't require extra memory, but the trade-off is that a bad pivot choice can tank the performance from a fast O(n log n) down to a slow O(n^2). Seeing the partitioning process step by step made it much easier to understand how the elements are actually swapped around the pivot to get them into the right spots. I also spent time looking at Binary Tree Traversals. It was helpful to see how Pre-order, In-order, and Post-order aren't just different ways to list nodes, but tools for different problems. For example, I realized that Post-order traversal is the ...
Post a Comment
Read more

Learning journal Week 3- CST370

-
This week I was learning and reading about the foundational concepts of algorithmic design, specifically Brute Force methodologies. I explored how these approaches, while conceptually straightforward, provide a comprehensive way to solve optimization problems by evaluating every possible solution. I also went through the examples like the Traveling Salesman Problem (TSP) and the Knapsack problem.  The homework (HW3) was a great way to put this into practice. For the DFS part, I had to be careful with sorting the adjacency list to make sure the stack processed neighbors in the correct numerical order. It was a good reminder that the data structure details really matter. Then for the TSP program, generating all those permutations to find the cheapest path really proved the point about how computationally expensive exhaustive search is. It was satisfying to finally get the correct path costs after reviewing the logic for a bit. I also looked into the theory side of Graph Traversal and...
Post a Comment
Read more

Week 2 Learning Journal - CST370

-
This week covered asymptotic notations and algorithm analysis, which felt math-heavy at first but started making sense once I applied it to my homework. The textbook reading explained the three main notations: Big-O for worst-case upper bounds, Big-Omega for best-case lower bounds, and Big-Theta for when both are the same. I found the Theta notation video helpful because it showed concrete examples of when to use each one. The best part of this week was seeing how analysis applies to real code through both homework problems. HW2_1 (Closest Pair Problem): I needed to find the minimum distance between any two numbers in an array. The brute force approach would compare every pair, which takes quadratic time. Instead, I sorted the array first and then scanned consecutive elements. This is much faster because sorting takes n log n time and scanning takes linear time. After sorting, the minimum distance must be between adjacent elements, so I only needed one pass through the array. HW2_2 ...
Post a Comment
Read more

Learning journal Week 1- CST370

-
This first week was a solid refresher. I started by watching the video on Euclid's algorithm for GCD. It was insightful to compare it against the basic consecutive integer checking method because it proved that brute force is not always the best answer. Sometimes a simple mathematical insight saves more time than a faster computer ever could. I also worked on Homework 1 this week. The assignment asked us to check for palindromes while ignoring symbols and case. I chose to create a new filtered string with only alphanumeric characters first. It was a good exercise, but it made me think back to the Algorithm Analysis Framework videos. Since I created a new string, I effectively used extra memory space. This connects directly to the space and time tradeoffs mentioned in the syllabus. I also spent some time reviewing the Graph representations and Trees videos. I realized I need to be careful about choosing between adjacency matrices and lists depending on whether the graph is weighted ...
Post a Comment
Read more