Learning Journal

This week we learned two new sorting techniques, counting sort and radix sort, both of which sort a set of inputted values without needing to compare them to one another. The counting sort finds the frequency of each value within the set then determines how they must be distributed by calculating the accumulation of the frequencies from the lowest end of the range to the highest end. Instead of evaluating each value as a whole, the radix sort involves looking at the individual digits of each value and distributes them based on a range of 0 to 9, repeating the process until each value has been distributed from their least significant digit (LSD) to their first (or leading) digit. We also learned about dynamic programming, which is where we can save computations when solving a problem that involves recalculating it's subproblems multiple times by saving the solutions to those subproblems in an array that can be referred to later rather than recalculating. We learned to apply this tec...

 This week we learned about two more trees: AVL and 2-3, as well as about heaps and hashing. AVL trees are balanced binary search trees that have a difference between the left and right subtrees of -1, 0, or 1. This difference is referred to as the balance factor (or balancing factor) and is specifically defined by the height of the left subtree minus the height of the right subtree. 2-3 trees on the other hand have subtrees with the same height and each node can have one or two values, where most other trees we've worked with have only one value per node. Heaps are complete binary trees, which consist of every level but the last needing to be completely filled and the last level orienting the existing nodes as far to the left as possible. Heaps are also defined by how the parent nodes relate to the child nodes, where each node in max heaps are greater than or equal to the numbers of its children and each node in min heaps are less than or equal to the numbers of its children. We l...

 This week we learned about the quicksort algorithm, binary tree traversal, and decrease and conquer algorithms. The quicksort algorithm uses the divide and conquer approach like merge sort, but partitions based on a particular value referred to as the pivot. The pivot is typically the first element within a given array, but sometimes we apply the median of three rule instead, which involves comparing and sorting the order of the first, middle, and last elements with the array and selecting the middle one as the pivot. As for binary tree traversal, we learned the three order variations using for moving through a tree (preorder, inorder, and postorder) and how to determine a tree's height (the length of the longest path from the root to the leaf node in the tree). In terms of decrease and conquer, the technique is based on the idea that smaller problems are solved more easily and we learned there are three variations: decrease by a constant, decrease by a constant factor, and variab...

This week we only learned about merge sorting, which involves using a divide-and-conquer approach to sorting the contents of an array. Given an unsorted array, merge sorting requires dividing the array into halves, referred to as subarrays. The subarrays are continuously divided into smaller subarrays until we are left with individual elements. Each of those elements are then compare against another and placed within a new array in a sorted fashion. Those arrays are then compared and combined with others until we are left with an array in similar size and content of the original one, though now sorted.

 This week we learned more about brute-force algorithms and were introduced to divide and conquer algorithms. We learned how brute-force could be applied to find whether or not one string appears as a substring within another, which can involve comparing every character of the string in question or the majority of them multiple times. When applying brute-force to combinatorial problems, we can resort to the exhaustive search, which involves generating all potential solutions or possible cases to a problem and evaluate each of them to determine which is the most suitable solution. Additionally, brute-force can be applied to graphs using either the Depth-first algorithm, which utilizes a stack for it's operation, or the and the Breadth-fist algorithm, which utilizes a queue for it's operation. Rather than using brute-force to find the solution to a problem, divide and conquer algorithms split problems into smaller problems, referred to as subproblems, that can be solved quickly a...

 This week we learned about using asymptotic notations for analyzing both non-recursive and recursive algorithms. The three notations used for algorithm analysis are referred to as Big Oh ( O(f(n)) ), Big Theta ( Θ(f(n)) ), and Big Omega ( Ω(f(n)) ). These notations are used to represent an algorithm's efficiency based on their respective order of growth in the best-case scenario ( Big Omega - Ω ), worst-case scenario ( Big Oh - O ), and/or when all cases have the same growth ( Big Theta - Θ ). For non-recursive algorithms, the low order terms and constant coefficients must be eliminated to identify the order of growth, while in recursive algorithms, the recurrence relation and initial condition must be defined first so they can be applied during the backward substitution process used to reach the order of growth. In relation to algorithm analysis, we also learned about the brute-force approach, which involves solving a problem in the simplest way.