My CSUMB Learning Journal

This week’s module focused on dynamic programming and graph algorithms, specifically the maximum coin collection problem and the Floyd algorithm for all-pairs shortest paths. In the first lab, we implemented a dynamic programming solution on an n by m grid, carefully constructing a DP table to compute the maximum number of coins that can be collected when moving only right or down. The most important part was understanding how the recurrence relation builds optimal solutions from smaller subproblems. We also practiced reconstructing the optimal path and handling tie-breaking rules correctly. In the second lab, we implemented Floyd’s algorithm using a triple nested loop structure to update shortest path distances. This reinforced the concept of gradually improving solutions through intermediate vertices and understanding O(n^3) time complexity.

This week’s module helped me strengthen my understanding of heap structures and hash tables through hands-on Java implementation. In the first lab, I implemented a max heap that supported insertion, deletion of the maximum element, checking whether an array satisfied heap properties, and rebuilding the heap when necessary. Writing the sift-up and sift-down operations from scratch helped me better understand how heap order is maintained after structural changes. In the second lab, I implemented linear probing with rehashing when the load factor exceeded 0.5. Reinserting all keys into a newly sized prime table made me clearly understand how resizing preserves performance. These labs reinforced how theoretical data structure concepts translate into practical code.

This week I focused on implementing sorting and graph algorithms in Java. I developed quicksort using Hoare’s partition method exactly as shown in the pseudocode and made sure to handle boundary issues carefully. I also implemented insertion sort and compared their performance using System.nanoTime to measure elapsed time. Testing different input orders helped me understand how recursion depth affects quicksort, especially with ascending data. In addition, I implemented Kahn’s algorithm for topological sorting in Java, computing in-degrees and processing vertices in ascending order. These labs strengthened my understanding of algorithm behavior and efficiency in practical Java implementations.

This week I focused heavily on preparing for the midterm by reviewing all of the core topics we have covered so far in the course. I went back over fundamental data structures such as trees, binary search trees, and graphs, including different graph types and representations like adjacency lists and matrices. I also reviewed important algorithm concepts such as merge sort and the divide and conquer approach, especially how merging works and why the time complexity is Θ(n log n). In addition, I practiced time complexity analysis, recurrence relations, and the Master Theorem, along with BFS, DFS, and classic problems like TSP and Knapsack.