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.

CST370 - Week 5

This week, we were introduced to the Quicksort algorithm, which is an efficient sorting technique based on the divide-and-conquer strategy. It works by selecting a pivot element from an array and then partitioning the remaining elements into two subarrays, one containing elements less than the pivot and the other containing elements greater than the pivot.

Additionally, we covered binary tree traversals and how to calculate the height of a binary tree. We also learned about the decrease-and-conquer technique, which involves reducing a problem to a smaller instance of the same problem and applying the solution recursively. An example of this is binary search, where the list is reduced by half at each step.

Lastly, we explored topological sorting using Directed Acyclic Graphs (DAGs) and Kahn's Algorithm, which relies on tracking the in-degree of each vertex and a queue. The in-degree represents the number of edges directed into a vertex. For instance, if vertex C has edges directed at it from vertices B and D, its in-degree is 2. 

In the programming homework, we implemented topological sorting using Kahn's Algorithm, as well as calculated the height of a binary tree. Overall, I felt that my understanding of this week's material was strong.

CST370 - Week 4

This week, we primarily focused on preparing for the midterm exam, but we were also introduced to a new sorting algorithm: Merge Sort. Merge Sort uses the divide-and-conquer technique by dividing the input into two halves, sorting them, and then merging them back together to form a sorted array.

As for the midterm itself, I wasn't too happy with my performance. I didn't sleep well leading up to the exam, so I felt a bit out of it. My biggest regret was not practicing more recursive algorithm problems beforehand. I had a general understanding, but I blanked during the exam and messed up the process. Besides the recursive questions, there were a few problems I didn't quite understand how to approach, and I accidentally misclicked the wrong answer on one question because I rushed a bit at the start.

Moving forward, I plan to review all the problems I got wrong during the exam and make sure I understand how to solve them, so I’m better prepared.

CST370 - Week 3

This week in Design and Analysis of Algorithms, we mainly covered various searching techniques, including brute-force exhaustive search, depth-first search, breadth-first search, and divide-and-conquer strategies. There wasn't too much reading assigned, and I felt the videos did an excellent job explaining the material. I'd say I still need to learn more about divide and conquer to feel fully confident in it, but I felt comfortable with everything else while taking the weekly quiz.

I did run into some trouble with the coding homework, specifically getting the output to match what was expected, but overall, I think the week went pretty well. The midterm exam is coming up soon, and I'm a bit nervous about it, but I'm hoping to brush up on my weaker areas before then.

CST370 - Week 2

In the second week of my Design and Analysis of Algorithms course, we focused on analyzing the time efficiency of algorithms. We were introduced to three types of Asymptotic Notation: Big O, Big Theta, and Big Omega. Of these, Big O and Big Theta are the most commonly used. At first, I found these concepts a bit challenging to grasp, but after watching a few supplemental videos, I feel I now have a decent understanding.

We also covered recursive algorithms and how to analyze them. I’m not entirely confident yet when it comes to solving recursive problems, but I believe I’ll get there with more practice.

Aside from the main topics, the overall reading load this week was lighter, which I appreciated. However, I found the puzzles particularly difficult. I often have trouble wrapping my head around them, and I think I spent at least an hour on the puzzle in our quiz.

CST370 - Week 1

With this week wrapping up, I have completed the first week of the Design and Analysis of Algorithms class. There was quite a bit of reading, and the information is somewhat dense, but I've been managing so far. Alongside our readings, we usually have some puzzles, which I honestly enjoy. They can be fun and sometimes confusing, but overall, I find them good. The programming homework has been fairly relaxed, which is nice given the reading load, though the quiz was quite tough. This week's programming assignment was a simple program to determine whether a user's input is a palindrome, and I wrote my program in Java.

In terms of the material, we have had a basic introduction to algorithms, covering topics like Euclid's algorithm for calculating the GCD and other methods for finding the GCD. I learned a bit about reading pseudocode in the context of algorithms, which initially seemed confusing but became clearer as I learned more. We briefly covered sorting and searching algorithms, then moved on to graphs, including unweighted and weighted graphs, and learned about adjacency matrices and lists, along with lots of related terminology. The graph section wasn't difficult to understand, but there is a lot of terminology I still need to refer back to. The most challenging part for me was algorithm analysis, specifically determining time complexities and identifying basic operations. For some reason, this took me longer to grasp, and I still don't have a complete understanding yet.

It's been a challenging first week, and I'm still working on fully grasping some of the terminology and concepts, but overall, I'm enjoying the course so far.