CS Learning Journal

  WELCOME TO WEEK 6 Learning Journal - CST 370 This week, we learned a lot of new material. However, the topics I found most interesting and fun to work on in the exercise problems were AVL and 2-3 Trees. First, we started by learning about two types of balanced binary search trees: AVL Trees and 2-3 Trees. These balanced BSTs make search operations more efficient compared to unbalanced BSTs. For a BST to be classified as an AVL or 2-3 Tree, it must meet certain qualifications. For example, an AVL Tree must have a balance factor of -1, 0, or 1 for each node. They can become unbalanced when an insertion or deletion occurs. We learned how to rebalance them by applying rotations, including right rotation (R rotation), left rotation (L rotation), left-right rotation (LR rotation), and right-left rotation (RL rotation). For 2-3 Trees , the qualifications are as follows: each non-leaf node can have 2 or 3 children, each node can have 1 or 2 keys, and all leaves must be at the same leve...

  WELCOME TO WEEK 5 Learning Journal - CST 370 This week, we learned a lot of new material. We started with an introduction to the quicksort algorithm, which is a divide-and-conquer based algorithm. We came to learn that it is generally more efficient than insertion sort and, in many cases, even merge sort ! We then covered binary tree traversals , which include preorder, inorder, and postorder . I had already learned these in the past, but it was good to review them! I almost forgot about them, and I must admit I had to do a little more research to fully understand them again. Eventually, once I grasped the concepts, they became much easier to understand. Next, we were introduced to the decrease-and-conquer technique, which is based on reducing a problem’s instance and solving it incrementally. Once the smaller instances are solved, we extend their solutions to the original problem. There are three variations of decrease-and-conquer :  Decrease by a constant (e.g., topol...

WELCOME TO WEEK 4 Learning Journal - CST 370 This week, we learned about Merge Sort , which uses the divide and conquer technique. It splits an array A into two halves recursively until each subarray contains only one element. After that, the algorithm begins merging and comparing elements in order to place them in sorted order, combining them back into the original array. This process is done recursively. The merge operation works by comparing the first elements of two subarrays, B and C . The smaller element is added to A , and the index (or pointer) of the corresponding subarray is incremented to move to the next element. This process continues until all elements from B and C have been merged into A , resulting in a fully sorted array.  The time efficiency of Merge Sort is determined using the Master Theorem . It falls under case 2 , not case 3, meaning its time complexity is Θ(n log n) . This makes Merge Sort an efficient algorithm, especially for large datasets, as it c...

  WELCOME TO WEEK 3 Learning Journal - CST 370  This week, we learned a lot. We started with Brute-Force String Matching , an algorithm that aligns the pattern against the first characters of the text and begins to match pairs of characters from left to right. It continues this process until there is either a match or, in the worst case, the pattern is not found in the text at all. The best case occurs when the first characters in the text immediately match the pattern. Next, we learned about Exhaustive Search and its application to three important problems. Exhaustive Search is simply a brute-force approach to combinatorial problems such as permutations, combinations, and subsets of a given set. The first problem we covered was the Traveling Salesman Problem , which involves finding the shortest path through a set of cities (visiting each city exactly once) and returning to the starting city. It is also described as the problem of finding the shortest Hamiltonian cycle. The...

  WELCOME TO WEEK 2 Learning Journal - CST 370  This week, I learned about the Analysis of Algorithms . First, we reviewed the topic of time efficiency notations , focusing on three key types: Big O Notation , Big-Theta Notation , and Big-Omega Notation . Big O Notation represents the upper bound, meaning it describes all functions with the same or lower order of growth as f(n). Big-Theta Notation represents the exact bound, meaning it includes all functions with the same order of growth as f(n). Big-Omega Notation represents the lower bound, meaning it captures all functions with the same or higher order of growth as f(n).      We also revisited the orders of growth , which, to be honest, I had forgotten about. Luckily, we reviewed them this week to help us better analyze algorithms and identify their time complexity or order of growth. The eight most common categories we covered were: 1, log n, n, n log n, n², n³, 2ⁿ, and n!. To figure out the order of gro...

  WELCOME TO WEEK 1 Learning Journal - CST 370  Oh, we’re back! A year into the program and a year left to go. I’m very excited for the coming year and all the classes left to take. The class I’m starting with this year is CST 370 - Design and Analysis of Algorithms . So far this week, we’ve reviewed and learned material like data structures. We got an introduction to algorithms and why they’re important. We covered Euclid’s algorithm for finding the greatest common divisor (GCD) of two numbers. Then, we talked about important problem types that drive algorithms, such as sorting, searching, and string processing. These problem types define what must be accomplished by an algorithm. To further explore algorithms, we reviewed some familiar data structures like linked lists (both singly and doubly linked), stacks , queues , and graphs . This week, we focused a lot on graphs and trees , which will be very important throughout the course. We started with the basics of graphs, in...