-

 

Week 3 – CST370 – Design and Analysis of Algorithms

This week we learned about Brute Force String Matching and Exhaustive Search. We also learned about Depth-First search and Breadth-First search.

Brute Force String Matching is an algorithm used to match a pattern against a string. You align the pattern against the first m characters from left to right until either all the m pairs of the characters match or a mismatching pair is encountered. If a mismatch happens, you simply shift the pattern one character to the right and begin the process again.

Exhaustive search is a brute-force approach to combinatorial problems. Some of these problems include the traveling salesman problem, knapsack problem, and assignment problem. The traveling salesman problem is an algorithm that finds the shortest route through a given number of cities that visits all cities and ends up at the starting city. This problem is ideal when dealing with weighted graphs. The knapsack problem involves items of known weight and value and a knapsack with a limited capacity. The object is to figure out what items accumulate the greatest value within the capacity of the knapsack. Lastly, the assignment problem requires you to assign n number of people n number of jobs, one person per job. The problem is to find an assignment with the minimum total cost.

Depth-First search is an algorithm that can be applied to process all vertices and edges of a graph. It starts the traversal at an arbitrary vertex by marking it visited. On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in. If there are several vertices, you can use alphabetical order to proceed to the next unvisited vertex. This continues until you reach a dead-end, where the algorithm backs up one vertex and continues visiting unvisited vertices. It is convenient to use a stack to trace the operation of depth-first search.

Breadth-First search is similar to depth-first but instead it proceeds in a concentric manner by visiting first all the vertices that are adjacent to a starting vertex, then all unvisited vertices two edges apart from it and so on until all vertices in the same connected component as the starting vertex are visited. For Breadth-First, it is convenient to use a queue to trace the operation.

 

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