CST370 - Week 7

 Studying for the final this week went smoother than expected. My biggest concern was getting a grasp on AVL and 2-3 trees. For whatever reason, constructing these trees just wasn't clicking for me, but after working through some practice problems, I'm feeling more comfortable with the material. The last module introduced Djikstra's algorithm, which determines the shortest path from a single source vertex to each of the other vertices. This algorithm is widely known and used for GPS, internet routing, etc. My favorite algorithm from the last two modules is probably Prim's algorithm. Something about finding the minimum spanning tree was just really fun for me to work through.

CST370 - Week 6

 For this week, we went over what makes an AVL tree, 2-3 trees, and heaps. Luckily most of this was familiar to me from my data structures class, as my biggest challenge this week was finding time to work on homework due to a busy holiday weekend at my job. Part 1 of the coding assignment had to do with "heapifying" a data set to maintain a max heap, or a heap where every parent is larger than both its children. The second part of this week's module had to do with hashing and how to handle collisions. We went over two strategies for handling collisions - "separate chaining" and "linear probing". For the coding assignment, we wrote a program that would take in user commands (for example, "insert 20") and hash/rehash the map as necessary. In the instance of a collision, it will simulate the steps of linear probing. I had a lot of fun with this assignment actually, even though I had to finish it in quite a rush. It was a good review of unordered_maps in C++ and I got a much more thorough understanding of how a rehashing works.

CST370 - Week 5

 This week we spent time covering tree traversals, the quicksort algorithm and topological ordering. When I first read up on Khan's algorithm, I expected it to be harder to understand, but I was glad to realize it was quick to pick up. The challenge for me came when writing the code to implement topological ordering. I had no problem with the basic implementation, but I had trouble when the input data contained two source nodes. I was eventually able to figure out my mistake and got the code working. Another challenge for me was the last question of the quiz that involved the King's puzzle. I realized that my ability to recognize a pattern and turn it into a mathematical formula was a little rusty. This is definitely something I should brush up on before the final exam.

CST370 - Week 4

 This week I spent the majority of time studying for the midterm. My main concern was finding and analyzing the recursive relation of certain algorithms, but I managed to do any and all practice problems and something finally clicked for me regarding that topic and it makes much more sense than it did originally.

Week 4 introduced the merge sort algorithm. While it can seem complicated at first it really is just one use of the divide and conquer strategy, where we break down the problem into smaller parts and then solve the more manageable parts before merging the pieces back together.

CST370 - Week 3

In this week's module, we covered brute force & exhaustive search, breadth-first search, depth-first search, and the master theorem. Brute force is a simple method of solving problems by just trying every possible outcome. For example, when considering the traveling salesman problem, just attempt all the possible paths and compare them to find which is the least cost. Breadth-first searches consider all the nodes at one level of a graph, before moving onto the next while depth-first searches involve following a path to its deepest point before coming back and checking other routes. Luckily, these were problems I'd practiced often in the path so I felt a little more confident with the material this week.

For the first part of the homework, we were to output a mark array after simulating a depth-first search. This part wasn't so bad to implement once I drew out the logic. The second part was a little more tricky to figure out. We needed to use permutations to solve the traveling salesman problem. I managed to pass all the available tests, but I feel the way that I stored the data and compared routes was a little.. messy.. to say the least. Hopefully, I will have time to review my code with the professor or the TA once it has been graded.

CST370 - Week 2

 This week we covered time efficiency and asymptotic notations. There are three main types of notations when it comes to time efficiency (or time complexity): Big-O, Big-Theta, and Big-Omega, with Big-Omega being less commonly used. Big-O notation considers the upper bound -- Meaning all functions with lower or same order of growth as f(n). Big-Theta is more precise -- All functions with the same order of growth as f(n). While, Big-Omega is the lower bound -- meaning all functions with same or higher order of growth as f(n). To figure out the order of growth, you must consider the number of executions of the basic operation of the algorithm. To represent the order of growth in Big-O notation, you must find the dominant factor and eliminate coefficients. For example, if the number of executions can be represented by 0.5n³ + 500n², the dominant order is n³ and we eliminate the coefficient, so the order is O(n³).  Big-Theta is used to represent the average time, but cannot be used if the best and worst case efficiencies are different.

The most difficult part of this week for me was considering the mathematical part of analysis. Using backward substitution and establishing base conditions and recurrence relations is definitely something I need to review.

CST370 - Week 1

 For this week we were introduced to the basics of algorithms and their usefulness in computer science. After going through the lecture material, I realized that I'm decent at implementing algorithms practically, but I don't have a good understanding of what makes an algorithm a good one and how to determine operations vs basic operations, etc. This will definitely be something that I take time to review further as the class progresses. Another opportunity for me will be slowing down to review pseudocode. I noticed that I tend to assume I know what's going on and glance over the code too quickly when I should be taking the code line by line to make sure I'm fully understanding. One thing I am excited for is the mathematical side of this class. My math has gotten a little rusty over the years, but it used to be my favorite part of computer science, so I'm hoping to find that connection with it again.