CST 370 - Module 2

 Week 2,

This week's material focuses on the basics of analyzing non-recursive and recursive algorithms. Starting off, we were introduced to using asymptotic notation to describe the category of time efficiency of an algorithm. Using the time efficiency categories of last week (i.e. n, n*log(n), n^2) we can describe the algorithm in three ways. One, Big Oh Notation (O (f(n)) ), where all functions with lower or same order of growth as f(n) can be used to express the category of an algorithm. For instance, you can say n is expressed in O(n) or even O(n^2). Second, Big Theta ( Θ(f(n)) ), where all functions with the same order of growth as f(n). For example, you can say n is expressed in Θ(n), but not expressed in Θ(n^2) or Θ(log(n)). Finally, Big Omega ( Ω(f(n)) ), where all functions with same or higher order of growth as f(n). An example of this would be that you can say n^2 is expressed in Ω(n), but not expressed in Ω(n^3).

As mentioned previously, we also learned about analyzing non-recursive and recursive algorithms. For now, I will only mention non-recursive analysis. Given a data structure of some sort (for now, an array of n integer elements), and an algorithm which finds the max value in the array, we must first find the location of the basic operation. This is typically an operation found in the innermost loop of the function. We use this basic operation to consider how many times the algorithm loops to complete it's task, which in turn, tells us the general category of time complexity the algorithm lies in. In this example, the algorithm uses one while loop which goes through the whole array once . So the basic operation can be whatever call to compare, add, etc within this while loop. Knowing the basic operation lies in one while loop, which loops n times, we can safely say the time complexity of this algorithm is Θ(n).

I would recommend watching a video on this as it is easier to visualize how to analyze an algorithm as opposed to reading it from a short paragraph.

Skipping the analysis of recursive algorithms, we were also introduced to Brute-Force. To summarize, Brute-Force implies we use a straightforward approach to solving a problem. This wouldn't be the most efficient way to solve a problem, but it is a good starting point. For example, if we want to sort an array of numbers, we can simply keep looping through the entire array swapping numbers until all elements are sorted. An example of this would be the selection sort, where we scan the array to find the smallest element and swap it with the first element, then keep repeating, moving one element forward each time we swap. Though this algorithm finishes the task, there is no difference with the best case or worst case with the time efficiency, as we will always scan through the entire array multiple times.

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