Learning Journal

       This week, I learned about two different types of balanced trees and their associated algorithms: AVL Tree and 2-3 Tree. I also learned how to use the Heap data structure to efficiently find maximum and minimum values. Heap can be represented by the bottom-up algorithm. Finally, I learned to use Hashing for storing values in a dictionary/array to perform efficient search operations. AVL Trees Problem: Unbalanced trees result in operations that take O(n) time. AVL Tree : A balanced binary search tree. The difference between the heights on the left and right subtrees is either -1, 0, or 1. ( balance factor = height of left subtree - height of right subtree) Ex: Since each node has a balance factor of -1, 0, or 1, it is an AVL tree. AVL Tree Rotations Rotation : A local transformation of a subtree whose balance factor has become either +2 or -2. Four types of rotations: R(right)-rotation, L(left)-rotation, LR-rotation, RL- rotation Ex:     A   ...

 This week, I learned to apply the "Divide-and-conquer" technique in a sorting algorithm, known as "Quick-sort." I also learned about "Decrease-and-conquer", which is a similar technique to divide-and-conquer and is used in sorting algorithms, such as "Insertion sort" and Khan's algorithm. A third technique I learned is the "Transform-and-Conquer" technique, which is used in "Pre-sorting." I also began to understand the efficiency of the algorithms used for Binary Tree traversal and height calculation. Quicksort Uses the Divide-and-conquer technique. It is "in place", like insertion sort, but not like merge sort (does not take up extra space) Quicksort of an n-element array: 1. Divide: Partition the array into two subarrays around a pivot x such that elements in lower subarray < x < elements in upper subarray 2. Conquer: Recursively sort the two subarrays. 3. Combine Example of Partitioning Worst case: O(n^...

 This week, I learned about the merge sort algorithm, an algorithm that uses the divide-and-conquer technique for sorting. Basic Idea     1. Split the input array into two halves     2. Sort the first half of the input array recursively     3. Sort the second half of the input array recursively     4. Merge the two sorted halves together Merge of the two sorted array B and C: 1) Compare the first element in arrays B and C 2) The smaller element is added to array A 3) The index of the array with the smaller element is increased by one (pointing to the next element) 4) Repeat until all elements from B and C are copied into A (sorted) Example: Time Analysis Of Merge Sort Algo: Mergesort(A[0, ... n-1]) if n > 1     copy A[0..[n/2]] to B[0..[n/2]-1]     copy A[n/2.. n-1] to C[0.. [n/2] - 1]     Mergesort(B[0..[n/2]-1]     Mergesort(C[0..[n/2]-1])     Merge(B, C, A) Recurrence relation:  ...

     This week, I learned multiple algorithms that apply different techniques to solving problems. They include Brute force and Divide-and-Conquer. Brute-force String Matching Given a string of n characters, text, and a string of m characters called the pattern, find a substring of the text that matches the pattern. Basic idea for solving string problems with Brute Force 1. Character by character comparison 2. If a mismatch occurs, shift a character and restart the comparison Efficiency for best case: If there is an immediate match, minimum number of comparisons will occur. (m) E.g. - Text: CSUMBGO - Pattern: CSU Efficiency for worst case: If there is no matching pattern, may iterate through entire text. Exhaustive Search and TSP Exhaustive search : A brute-force approach to solving combinatorial problems. Basic idea:     1. Generate all potential solutions (or all possible cases) to the problems.     2. Evaluate each case one by one     3. D...

 This week, I learned to mathematically analyze algorithms using Asymptotic notations on algorithms such as non-recursive and recursive. Asymptotic Notations Algorithm analysis is to identify the time category of an algorithm (time complexity). The most common categories are: 1, log n, n, nlogn, n^2, n^3, 2^n, n! Three notations that represent an algorithm's efficiency: O(f(n)) <- upper bound ,  Θ  (f(n)) <- tight bound , and  Ω (f(n)) <- lower bound . f(n) written as O(n^2), Θ (n), Ω(nlogn) Upper bound : All functions with lower or same order of growth as f(n). Ex: f(n) = O(n^2) Functions that satisfy: 1, n, nlogn, n^2, 5n, 7n^2, 500.  Tight bound : All functions with the same order of growth as f(n). Ex: f(n) =  Θ (n). Functions that satisfy: 4n, 20n Lower bound : All functions with same or higher order of growth as f(n). Ex: f(n) =  Ω (n*logn). Functions that satisfy: n*logn, n, n^2, n^3, 4n^3  Two Rules to Simplify T(n) T(n) => ...

 This week I learned what Algorithms are, important problem types in Algorithms, fundamental data structures, and analysis of algorithms. Algorithm: A sequence of clear instructions for solving a problem. Algorithms produce output in a finite amount of time. It is advised to solve a problem by choosing the right algorithm first before coding the solution. Euclid's Algorithm: An algorithm used to calculate GCD (Greatest Common Devisor). The GCD is the largest integer that divides both m and n evenly, with a remainder of zero. m and n can't be 0 at the same time. If one of the two values m or n is 0, the other non-zero input is the answer. (e.g. gcd(60,0) = 60) Ex:  gcd(0,0): 0/0 = Invalid gcd(6, 4) Numbers that can divide evenly between both: 1, 2, 3  (Can't divide 4), 4  (Can't divide 6) Largest is 2, so answer is 2. Euclid's algorithm is: gcd(m, n) = gcd(n, m mod n) until n becomes 0. At that point, m is the answer. Ex: gcd(60, 24) = gcd(24, 60 mod 24) = gcd (24, ...