CST 370 - Module 5

 Week 5,

This module's material covered some more algorithms using divide and conquer. One of these algorithms is the quicksort algorithm. The goal of quicksort is to partition the array into two subarrays around a pivot. From there, we recursively sort the two subarrays, then combine the results. The Big Oh notation for quicksort is O(n*log(n)), which is similar to merge sort, however, when dealing with large sorting operations, quicksort beats merge sort by a small margin. 

Next, we talk about a divide and conquer ready data structure called a binary tree. Data is usually inserted to the left or the right of a root node, typically by smaller numbers to the left of the node, and greater numbers to the right. This continues further and further down the tree creating what could be describe as... well... a tree. The main problem with using this data structure is how to traverse the binary tree. In short (got to leave some room for you to research), we talk about three methods, pre-order (root->left->right), in-order (left->root->right), and post-order (left->right->root).

The next important bit of material covered introduced us to decrease and conquer. Decrease and conquer is a technique that solves problems by first making the problem smaller, as it would be easier. There are a couple ways of doing this. Decreasing by a constant, constant factor, and variable size decrease. One real example of a decrease and conquer algorithm is the binary search. When given a key or value to look for within an array, we start in the middle index of the array, if the value is smaller than the key, then we look at the value in the middle of the subarray to the right. If the value is greater than the key, then we look at the middle of the subarray to the left. repeat until we find the value. Every time we compare a value to the key, we cut down the number of elements we compare in half. The Big Oh notation of this would be O(log(n)).

Another topic introduced was DAG (Directed Acyclic Graph) and how we can determine if a directed graph has a cycle or not (DAG if there is no cycle). One way to find this is using Kahn's Algorithm, where we find the topological order using source removal, where we eliminate a vertex or vertices with 0 incoming vertices. After each removal, a vertex or vertices will have one less incoming vertex. If we manage to eliminate all vertices, the graph is indeed a DAG. If we end up with being unable to remove all the vertices, then the graph is not a DAG.

Comments

Post a Comment

Popular posts from this blog

CST 338 - Module 4

 This week in CST 338, there were few assignments to complete. This time we got to get our hands on Android Studio, where we created very simple app where android users can convert temperature °c to temperature °f, or vice versa. We also got to complete our first project, where we practiced inheritance using an abstract class, and concrete classes. However, besides that, we were also allowed to go back to our previous assignment, Markov, and have our teammates review each other's code. I worked with my teammate Ryan Matsuo  and after reviewing his code, I learned a few things that could help me in the future, like splitting a string using str.split() with a regex of "\\s+" instead of what I did which was more complicated. My strategy with solving the Markov assignment was that I started writing the code right away. I didn't put anything to practice into paper because I feel I can do the same thing in the code. I would read the prompt, create stubs for the methods to b...
Read more

CST 363 - Module 7

 Week 7! This week involved involves us using a NoSQL database called MongoDB. After using both MySQL and MongoDB and the instructions that came with it, I can certainly say that there are a few differences between MySQL and MongoDB.  For instance, MongoDB is not relational, whereas SQL is. Mongo and SQL use different query languages. And Mongo doesn't use transactions but SQL does. Some similarities however, include both SQL and Mongo supporting things like query projection, unique keys, and indexes. One thing that is strengthened on Mongo, is replication, which increases reliability which can be useful when an error occurs. When it comes to my preferred choice of the two databases, it depends. MySQL's language is more human based or easier to read, but it doesn't make it easier to find very specific data from multiple schemas. However, if you are already familiar with coding in JavaScript, or coding in general, then MongoDB can be strong choice as it is easier to support ...
Read more

CST 363 Module - 1

 CST 363! This is the start of the next course in CSUMB's Computer Science Online program. It is an introduction to databases using SQL. Thankfully due to the previous course in software design, I had a small introduction to using databases.  I have also come to understand the more distinct difference between relational databases and spreadsheets. One major difference is the fact that databases are more useful for working with large amounts of data, working with other tables of data, and can perform queries faster. Reasons as to why this is important, or beneficial compared to using spreadsheets or writing into a file is more related in how you use it. For instance, instead of looking through a large portion of data to find a small number of rows, you have the option to search through a subset of data, making tasks much easier to complete. Databases can also have additional security, only allowing certain data to be seen by different programs. Especially if you have multiple p...
Read more