CST370 - Week 7

Wrapping up our 7th week in Design & Analysis of Algorithms, we covered some new non-comparison sorting algorithms: Counting Sort and Radix Sort. Then we had a lecture on Dynamic Programming, whose basic concept is to break a problem into smaller subproblems and optimize by storing the results of those subproblems so we don't compute the same ones multiple times.

Next, we went over Warshall's Algorithm and Floyd's Algorithm, which look quite similar but have different purposes. Warshall's algorithm finds the transitive closure; in other words, it determines whether there is a path between two vertices. In contrast, Floyd's algorithm is used to find the shortest paths/minimum cost between vertices.

Lastly, we discussed the Greedy Technique, which involves building a solution step-by-step by always making the choice that seems best at the moment, with the hope that these local choices lead to an optimal overall outcome.

Next week we have our final exam, which I'm a bit nervous about. To prepare for it, I plan to review all the material we've covered so far in the previous weeks and work through previous problems in our quizzes and midterm.

CST370 - Week 6

This week, we covered several new topics, including AVL Trees, where we practiced inserting nodes and balancing the tree using rotations. We also learned about 2-3 Trees and how to build them from a set of values. The topic we focused on the most, though, was probably Heaps.

A heap is a special kind of binary tree with two conditions:

• It must be a complete binary tree, meaning every level is completely filled except possibly the last, which is filled from left to right
• 
  
• It must follow the heap property. In a max heap, each parent node is greater than or equal to its children. In a min heap, each parent node is smaller than or equal to its children.

We also learned how to remove a value from a max heap and how to build a heap using a bottom-up method with an array. Additionally, we were briefly introduced to heapsort, a sorting algorithm that works in two steps:

• First, build a max heap from the list of numbers.
• 
  
• Then you repeatedly remove the largest number (which is at the root) and move it to the end of the array. After (n-1) removals, the numbers are sorted.

Lastly, we touched on hashing, which is used to store data efficiently. We also went over important concepts like collisions, load factor, and rehashing.

Overall, this week introduced a few topics I'd plan to revisit to strengthen my understanding. I plan to review the lectures on hashing and heaps, and watch some supplementary videos to better grasp the material.