-

 

Week 7 – CST370 – Design and Analysis of Algorithms

This week we learned about several programing techniques and algorithms. We started with counting sort, which is an algorithm that does not use comparison to sort. It is used to sort integer values in a range. The next algorithm we studied was the Radix sort algorithm. This algorithm is also non-comparison based and sorts numbers composed of digits and no range is required. You need to use the counting sort algorithm on each digit, and you sort them using the range 0-9 for decimal numbers.

We also covered dynamic programming. This is an algorithm design technique for solving problems with overlapping subproblems. Instead of solving overlapping subproblems over and over, you solve them once and record the results in a table from which a solution to the original problem can then be obtained. An example of this technique can be illustrated using Fibonacci Numbers where you must compute F(n) by adding F(n-1) + F(n-2) for n > 1. With Dynamic programming, we can use an array to keep the results of the previous two functions such as F[i] = F[i – 1] + F[i – 2].

The last three algorithms; Warshall’s Algorithm, Floyd’s Algorithm, and Prim’s Algorithm deal with graph traversals. Warshall’s and Floyd’s algorithms are based on a similar idea. Warshall’s algorithms uses transitive closure of a directed graph with n vertices and an n x n Boolean matrix. The cells in this matrix will have a 0 or a 1 if there exists a nontrivial path from the ith vertex to the jth vertex. Floyd’s algorithm uses a similar technique to find the lengths of the shortest paths from each vertex to all other vertices given a weighted connected graph.

Prim’s Algorithm connects vertices in the cheapest way possible so that there will be a path between every pair of points using a minimum spanning tree (MST). First, we start with a tree T1 consisting of a vertex. Next, we grow T1 by adding one vertex at a time. Next, we construct Ti + 1 from T1  by adding a vertex not in Ti that is closest to those already in Ti. Finally, we continue until all the vertices are included.

 

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