CST 370 - Module 7

 Week 7

 This module's material covers different algorithms for solving problems with graphs, and sorting.

For instance, we were introduced to non-comparison sorting such as the Counting Sort or Distribution Counting Sort, where we calculate the frequency of each value of a given list and determine distribution values via the sums of frequencies. What is interesting about Counting Sort is the fact that is stable, or the numbers with the same values stay in the same order as they do in the given list.

 A technique introduced was Dynamic Programming. One problem about using a brute force technique is that sometimes, we would use a recursive function, which depending on the problem we want to solve, can induce too many overlapped functions. Dynamic Programming will allow us to avoid this by using an array to keep solutions of sub-problems. When the solutions to the sub-problems are recorded in the array, we solve the original problem with that array.

The next two algorithms are very similar to each other and both solve problems related to graphs. Warshall's Algorithm computes the transitive closure of a directed graph, which tells us if a node is reachable from a given starting node. This uses something similar to an adjacency matrix, except instead of only having information on adjacent nodes, it has information on whether or not a node can reach another node. 

The other algorithm is Floyd's Algorithm, which determines the shortest paths between all pairs of nodes in a weighted graph. This also uses something similar to an adjacency matrix, except, instead of having information on just the neighboring nodes, it has information on both the reach-ability of the node and the shortest paths to each other.

There are more topics covered throughout the module, such as Radix Sort, solving the Coin Collecting Problem, the Greedy Technique, finding the Minimum Spanning Tree,  and Prim's Algorithm, but I leave that for you to research.

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