Edward's CS Journey

 Non-comparison Sorting, Dynamic programming, and the Greedy Technique Non-Comparison Sorting Non-comparison sorting is when sorting happens without comparing elements to each other. One method discussed this week is the counting sort. In counting sort, the frequency and distribution of elements are calculated for a set of inputs, and they are used to sort them in ascending or descending order. Below are the steps to complete a counting sort and an example of using a counting sort to place a set of integers in ascending order.  Create a table with a range of values and the frequency of each value.  Calculate the distribution of each element by adding up the frequency of the current element to the previous element.   Start with the last number in the original list of values and use the distribution to place an element in a specific position in an array Reduce the distribution for that element Repeat steps 3-4 for the next element in the list.  Counting Sort ...

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.