Cohort 23 CS Online Journal

CST370 Week 6 This week, we learned more about tree balancing and hashing.      AVL trees are self-balancing binary search trees where the balancing factor of each node is either 1 (left), 0, or -1 (right). The balancing factor is calculated by how many 'edges' traveled from the node to the last leaf it can reach (or the height of the subtree): Balancing factor = height of left subtree - height of right subtree      To maintain AVL trees, rotations may need to be made on nodes. For left-heavy trees (or subtrees), R-rotations are typically used, while right-heavy trees (or subtrees) use L-rotations. Rotations can be used multiple times in a row, like two R-rotations needed.      2-3 trees are binary search trees that must have at least 2 or 3 children to each node. Each node can contain one value or two values - if it has one value, it will have 2 children, and if it has two values, it will have 3 children. The children can contain one or two ...

CST370 Week 5 Binary trees: A divide-and-conquer ready data structure. There are three ways to traverse it: preorder, inorder, and postorder traversal methods. Preorder visits from root -> left -> right. Inorder visits from left -> root -> right. Postorder visits from left -> right -> root. Binary search: An application of the decrease-and-conquer algorithm. Complexity is (big O)(logn). Quicksort: For time complexity, the best case is n(logn), while the worst case is n^2. To perform a quicksort, we assign the first value of an array as the pivot, and recursively travel forward (i) and backward(j)  to find a spot where the pivot can create a partition. While traveling, we swap values of i and j whenever i > pivot and pivot > j. This should create a partition where all values preceding the pivot will be smaller than it, and all values after the pivot will be larger than it. Decrease-and-conquer: Technique to reduce the size of a problem into one smaller proble...

 CST370 Week 4 This week is a short week due to midterms. We learned about merge sort, which uses the divide-and-conquer method. Merge sort goes through these steps: Split the original array into two halves, until each individual element is by itself. Sort the first half recursively Sort the second half recursively Merge the two halves together: Compare the first elements of each half Push smaller element to a new result array Increment index of half that pushed the smaller element (Repeat Steps 1-3 until all elements are sorted) For Master Theorem, the time complexity of merge sort is  θ [n*log(n)]. There are two recursive calls, so a = 2, the input size divides by 2 each time, so b = 2, and since the number of comparisons is n, (n^d) = (n^1) => d = 1. I wanted to understand how to derive the Master Theorem from pseudocode, so I looked up some practice exercises online, but there is very little found for it. I decided to get the textbook because I need more exercises to un...

CST370 Week 3      This week I studied a lot more about recursion and search algorithms in order to understand the homework better.       We learned about brute force algorithms like exhaustive search, which is useful in finding all permutations of a set. Exhaustive search goes through each possible case and then identifies which of these cases is either most efficient or solves the problem. The time complexity for exhaustive search is dependent on the number of permutations it has [ (n - 1)! ].      There are two graph traversal algorithms: depth-first search (DFS) and breadth-first search (BFS).       DFS makes use of a stack and a mark array to determine what nodes have been visited, and creates a tree with tree edges. Time efficiency for DFS is dependent on the sum of the number of vertices and edges it has: 𝚯 (|v| + |e|).     BFS makes use of a queue and a mark array to determine what nodes have been v...

CST370 Week 2 Week 2: I still need more practice on the homework. I am rusty when it comes to manipulating vertices and displaying them correctly. The other homework about manipulating time differences was very easy in comparison.  I learned a great deal about recursion! Biggest concepts to me to not forget are: Big Om notation is an upper bound, so an algorithm must be the same order or lower growth as f(n). So, n^2 would not be within bounds for Omega notation of n. Big Theta notation is a tight bound, meaning an algorithm must remain within the same order of growth as f(n). So, n^2 or log(n) would not be within bounds for Theta notation of n, only n. Big Omega notation is a lower bound, so an algorithm must be the same order or higher growth as f(n). So, log(n) would not be within bounds for Omega notation of n.

CST370 - Week 1 New course! CST370 is Design & Analysis of Algorithms.  Currently, I am wracking my brain trying to remember C++. It's been a while, but I feel more comfortable working with it versus Java.  From what I've read, using pseudocode is the most fundamental way to begin thinking about making programs. Before even translating it to a language, try to walk through the algorithm in your head or on paper. If you find that the algorithm is frustrating to make sense of already, how do you even begin implementing it in code? (Well, you still can, but understanding how it works is why we're here.)  I remember one of the hardest concepts for me to grasp was binary tree traversal. I hope I get a lot more practice out of it in this class!