My CS Online Journey

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...

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...

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...

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 ...