CST370: Week 7 (Week 58)

 This week we covered non-comparison sorting, dynamic programming, Warshall's algorithm, Floyd's algorithm, Greedy Technique, and Prim's algorithm. This week was a heavier week and I'm glad that it's almost done. That said, I found the counting sort algorithm to be very interesting since it uses an approach that is different from standard comparison based sorting which is what we usually, intuitively would try. The dynamic programming problem based on coin collecting was also interesting to me since up until recently, dynamic programming was a popular topic for programming interviews.

Along with our programming assignment I completed the bonus homework assignment. I modified a red-black tree to simulate the one at the core of Linux's Completely Fair Scheduler (CFS). I saw it as an opportunity to catch up on points that I have missed while learning about something interesting that also applies to my career.  My example is VERY bare bones and simple. No preemption, no dynamic time slices (quanta), no priority factors and weights, no multi-CPU support, etc., but I learned a lot in the process.

CST370: Week 6 (Week 57)

This week we covered AVL trees, 2-3 trees, heap trees, and hashing. Hashing is a slight departure from the structures we've covered more recently since it's superficially represented as something other than a tree. That said, it's still a type of mapping construct/process. The rotation operations used in the addition, removal, and ordering/balancing operations of the trees was new. For AVL trees, the professor provided a YouTube video that was an excellent supplement to our recorded lecture. It helped clarify things for me.
https://www.youtube.com/watch?v=msU79oNPRJc

As an interesting footnote, I also liked the example approaches to confirming that a number is a prime number. I don't have a deep knowledge of cryptology and number theory but I have heard that prime numbers play a big role.
https://www.geeksforgeeks.org/cpp/c-program-to-check-prime-number/

As usual, I was curious about real world applications of the concepts introduced this week. I found that the red-black tree at the core of the Linux completely fair scheduler (CFS) is a type of 2-3 tree. I pointed this out in the class discord channel. It's been part of the Linux kernel since v2.6.
https://developer.ibm.com/tutorials/l-completely-fair-scheduler/

CST370: Week 5 (Week 56)

 This week we covered topological sorting, Kahn's algorithm, binary tree traversal, quick sort, and transform and conquer. We covered a broad range of algorithm concepts this week but to me there were two standouts. 1) I like that we coded an algorithm comparison as part of our assignment. Metrics and comparisons are a big part of the class so evaluating run time on the same system side by side is very helpful. I plan to try implementing a multithreaded vs single threaded example when I have time. 2) I enjoyed working on the King's Reach problem in the homework and on the quiz. It's a math focused puzzle and I enjoyed the process of breaking down the problem, recalling some of my algebra, and applying it in this context.

CST370: Week 4 (Week 55)

 This week we covered merge sort and though we didn't have a programming assignment I took some time to explore it. I watched some videos suggested by my classmates and did my own search to find out about some of its real world applications. I'm a fan of low level code and embedded systems so I looked at the Linux kernel. As it turns out, the list_sort algorithm in the kernel which is used to sort linked lists, is based on merge sort. One difference from other applications is that they use an iterative approach and avoid recursion. The iterative approach makes for more predictable memory usage, better constrained stack usage, and cuts down on function call overhead.

Linux 6.17 list_sort

We also had our midterm this week. The process of preparing, and in my case probably over preparing, helped make the concepts we covered more concrete in my mind. Specifically, preparing my four page note sheet. With the pace of the classes, sometimes I worry that too much of what is taught might wind up in short term memory and might not serve us when we need it. I think the process of exam prep definitely helps avoid that possibility.