-

 

Week 4 – CST370 – Design and Analysis of Algorithms

 This week we continued learning about the divide and conquer technique. We specifically learned how to apply it to the Mergesort algorithm. Mergesort sorts an array by dividing it into two halves and sorting those two halves recursively. Lastly, you merge the two sorted arrays into a single sorted array. The algorithm merges the two sorted arrays with two pointers that are initialized to point at the first elements of each array being merged. The two elements are compared and the element with smaller value is added to the new sorted array. The next step is to increment the index of the smaller element and the two elements are compared again. This is repeated until the end of an array is reached. At that point, the remaining elements of the other array are simply copied to the new array. One of the main advantages of Mergesort is that it always has a time complexity of O(n log n) regardless of the input data distribution which makes it well suited for large data sets.

 

 


Comments

Post a Comment

Popular posts from this blog

-
  Week 2 – CST370 – Design and Analysis of Algorithms This week we covered asymptotic notations, non-recursive algorithms, and recursive algorithms. We use the order of growth to determine an algorithm’s efficiency. We also use three notations to rank the order of growth: big oh, big omega, and big theta. Big oh, is the set of all functions with a lower or same order of growth as g(n), a simple function to compare the count with. Big omega is the set of all functions with a higher or same order of growth as g(n). Lastly, big theta is the set of all functions that have the same order of growth as g(n). Non-recursive algorithms solve problems by repetition through loops to execute instructions until a condition is met. An example of a non-recursive algorithm is a Max Element algorithm where you must find the value of the largest number in an array. A recursive algorithm calls itself with smaller values and returns the result for the current input by carrying out basic operati...
Read more
-
  Week 1 – CST370 – Design and Analysis of Algorithms This week was a combination of week 0 and week 1. We were required to set up a GitHub account, if we did not have one already, to complete our homework assignments with GitHub Classroom. Homework 0 required us to write a program that reads two integer numbers from a user and displays the sum and difference of the two numbers. We also needed to make sure that the difference between the two numbers is always 0 or positive. The purpose of Homework 0 was to get familiar with GitHub Classroom, set up our IDE environment, and submitting to Canvas. The topics covered this week included Euclid’s Algorithm for GCD calculation, important problem types, fundamental data structures, and algorithm analysis framework. Euclid’s Algorithm for GCD calculation is an algorithm that takes two numbers and finds the greatest common divisor by repeating the equality gcd(m, n) = gcd(n, m mod n) until m mod n is equal to zero. The last value of m wi...
Read more
-
  Week 1 – CST – 363 Introduction to Database Systems 1.       Relational database tables and spreadsheets look similar with both having rows and columns. What are some important differences between the two? Some important differences between database tables and spreadsheets are the way data is formatted and how data is stored. In a spreadsheet, every cell can store any type of data like a date, integer, or string. These data types can also have their unique format. In a database, each cell must contain only one data type helping to prevent data mismatch mistakes. In a spreadsheet, the data is stored in each cell. In a database, the data is stored in a row made up of columns. 2.       Installing and configurating a database and learning how to use it is more complicated than just reading and writing data to a file. What are some important reasons that make a database a useful investment of time? Learning how to install and c...
Read more