Edward's CS Journey

Trees, Heaps, and Hashing This week we learned about four types of data structures: AVL trees, 2-3 trees, heaps, and hashing.  AVL Trees AVL Trees are balanced binary search trees that have a balance factor. Balance factors are computed by taking the difference between the height of the left subtree and the height of the right subtree. An AVL tree is said to be balanced if the balance factor is -1, 0, or 1. If the tree is unbalanced, one of four rotations can be used to transform the binary search tree into a balanced tree: Left Rotation, Right Rotation, Left-Right Rotation, or Right-Left Rotation. Below is how to determine what rotation is needed:  Left Rotation:  The root has a negative number smaller than -1. Right Rotation: T he root has a positive number greater than 1.  Left-Right Rotation:  The root has a positive number greater than 1, and the node on the left has a negative number. In this case, we rotate the node with the negative number to the left an...

Topological Order - Khan's Algorithm This week, we learned how to topologically sort graphs using Khan's Algorithm. To be able to topologically sort a graph, we first need to determine that a graph has no cycles; in other words, it is a directed acyclic graph. If the graph has a cycle, we cannot determine a topological order. This process is similar to the depth-first search, except our topological order is reversed. The process is as follows:  Calculate the in-degree of each vertex. The in-degree is the number of incoming edges each vertex has.  Push the vertices with an in-degree of zero (no incoming edges) into a queue.  Remove the vertex from the queue, which removes all edges coming from that vertex.  Decrement of the in-degree for the neighboring vertices of the vertex that were removed from the queue.  Push any neighboring vertices with an in-degree of zero into the queue Repeat steps 3-5 for the next vertex in the queue until the queue is empty. Below is...

Mergesort  This week, we learned about the divide-and-conquer algorithm called mergesort. Mergesort uses two processes to sort an array: divide and merge. The algorithm starts off with a division process. Mergesort starts by dividing an array in half and storing each half in its own array. Each of those halves is cut in half again. The process continues until each element in the original array has its own array. The next process is the merge process. In this process, elements in each array are compared and merged in a sorted manner into another array. Two pointers are used to compare elements in each array to see which is greater/smaller. They are then merged into another array in the correct order. This process continues until all elements are in one array. The end result consists of all elements in one array where the elements are sorted in ascending order. The picture below shows this process for an array of numbers. 

 Brute Force Design Techniques and Divide-and-Conquer  This week, we learned about different exhaustive search algorithms that used a Brute-Force design technique. Exhaustive search algorithms consider every possible case before coming to a conclusion.  The first algorithm discussed was the sequential search and matching algorithm. This algorithm was presented in the form of searching a string to find a pattern, such as the one below. In this algorithm, every character in a string is checked for the pattern until the end of the pattern is reached. The efficiency of this algorithm is dependent on the text and pattern. In the example below, there are 16 characters in the text and 4 characters in the pattern that we are looking for. Since we are considering all comparisons and cases, we should have 13 shifts and 52 comparisons.  Another exhaustive search was conducted for combinatorics problems. An exhaustive search can be used to solve problems such as the Traveling Sa...

Asymptotic Notations  This week, we learned about asymptotic notation and its use when analyzing recursive and nonrecursive algorithms. Last week, we learned about identifying the basic operation of an algorithm, which is the operation that contributes the most to the total running time. After all operations of an algorithm are analyzed and a basic operation is found, we can assign a function to the algorithm that represents the time efficiency of the algorithm. There are 8 common time efficiencies that are used. These can be found below and are in order from fastest (top) to slowest (bottom):  Once a function is assigned, we can use one of three asymptotic bounds and notations to display the order of growth of an algorithm. The three types of notation that can be used when analyzing an algorithm: Big 'O' (oh) Big 'Θ' (theta) Big 'Ω' (omega) Big 'O' Notation Big 'O' is used as an upper asymptotic bound and is written as O(f(n)). This means that a...

Algorithms and Analysis Framework This was our first week in CST 370, which focused on algorithms and analysis frameworks. An algorithm is a "sequence of unambiguous instructions for solving a problem." When you describe the sequence of steps, there is only one way to interpret it. For example, when finding the greatest common denominator, we can use Euclid's algorithm, which is found below.  Euclid's algorithm (left) shows clear directions on how to find the greatest common denominator.  The right shows another method for finding the greatest common denominator, the Middle school procedure. This method is not considered an algorithm because prime factorization is not defined and is considered ambiguous, as there are multiple ways to find a number's prime factors.  Developing an algorithm is an important process before the code is developed. When a problem arises, the algorithms to solve the problem should be written out first before coding begins. The algorithm b...