CST370 Week 3

  This was our third week in CST 370 - Design and Analysis of Algorithms.

 Brute Force String Matching

The first algorithm we looked at this week was Brute Force String Matching. In this algorithm we loop through each character of a string. Then for each character we loop again, starting at that character, until we find the pattern we are looking for (in which case we return true) or find a character that does not match the pattern (in which case go back to the first loop.

Exhaustive Search

The class lecture defines Exhaustive Search (ES) as a Brute-Force approach to solve combinatorial problems. The basic concepts of Exhaustive Search are:

  • Generate all potential solutions (or all possible cases) to the problem.
  • Evaluate each case one by one.
  • Determine the solution among the possible cases.

Our class lecture discusses using ES to solve some different problems. 

Traveling Salesman Problem (TSP)

To solve this problem using ES we compute each permutation of the graph and their costs, then select the optimal permutations. Solving TSP in this way has a time efficiency of n!.

 

Knapsack Problem (KP)

To solve this problem using ES we calculate the weight and total value of all subsets of items. Solving KP in this way has a time efficiency of 2^n

 

Assignment Problem (AP)

To solve AP using ES we calculate the total hours of each possible permutation of the people in the matrix.

 

Depth-First Search (DFS)

From our textbook: "Depth-first search starts a graph’s traversal at an arbitrary vertex by marking it as visited. On each iteration, the algorithm proceeds to an unvisited vertex that is adjacent to the one it is currently in. This process continues until a dead end—a vertex with no adjacent unvisited vertices— is encountered. At a dead end, the algorithm backs up one edge to the vertex it came from and tries to continue visiting unvisited vertices from there. The algorithm eventually halts after backing up to the starting vertex, with the latter being a dead end."

 

Breadth-First Search (BFS)

From the textbook: "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 the vertices in the same connected component as the starting vertex are visited."

Divide and Conquer (DC)

Our class lecture defines DC as the following:

  • A problem is divided into several subproblems. Typically, it is divided into two subproblems.
  • Subproblems are solved (recursively until the size is small enough to solve right away).
  • If it's necessary, the subproblems' solutions are combined (or conquered) to get the solution of the original problem.

Master Theorem 

To calculate the time efficiency of a divide and conquer algorithm, we use a technique called Master Theorem. We have three items: b, a, and d.

  • b = Number of subproblems
  • a = Number of subproblems to be solved
  • d = the time to combine the original problem of size n.
  • We can use the following formula to get the items: T(n) = aT(n/b) + f(n)

Then we compare the different items:

  • If a < b^d, then Θ(n^d)
  • If a = b^d, then Θ(n^d * log n)
  • If a > b^d, then Θ(n^(logb a)

Comments

Post a Comment

Popular posts from this blog

Week 11

CST-338 Week 3  This week was the third week of CST-338. In this week we continued to learn more design and Java concepts. Black Box & White Box Testing This week we learned about two methodologies used for testing programs, black box and white box testing. Black box tests only focuses on the input, output, and functionality of a program, and not the internal code, logic, or structure of a program. One of the advantages of black box tests is that they are simple and easy to run. White box tests focus on the code, logic, and structure of a program. One of the advantages of white box tests is that can find logical errors, security vulnerabilities, or inefficiencies in code. Coupling & Cohesion This week we learned about coupling and cohesion in objects and methods. Coupling refers to how much different classes rely on each other. If two classes have tight coupling then they are more dependent, and changes in one are more likely to affect the other. If two classes have loose c...
Read more

Week 12

CST 338 - Week 4 This week was the fourth week is CST 338, also known as Software Engineering. In this week we began to learn about android development. Project 1 Review This week we finished a large project in CST 338. We have been asked to work with one or more classmates, and answer some questions about the project. With whom did you work? I worked with Nasser. What was your strategy for solving the assignments? My strategy was to read all of the method descriptions before I wrote any code. As I read them I created method stubs, and detailed TODO comments for each method. Afterwards, I started writing the methods from top to bottom in the assignment prompt. If a method called another method that I had not written yet, I would go ahead and write that method first so I better understood how they interacted. What was their strategy for solving the assignments? Their strategy was to follow the instructions closely as is, by following the UML diagrams and prompt as closely as possible. ...
Read more

Week 19

Image
 CST-363: Week 3 This is the third week of CST-363, also known as Intro. to Databases. Questions What is an SQL view.  How is it similar to a table? In what ways is it different? An SQL View stores a SELECT statement for later use, allowing the statement to be easily accessed in the future. A View functions similarly to a table, because SELECT statements return tables. However, the values that a View shows aren't being stored in the View, but the actual tables. This means that when one of those tables is updated, the View has to be as well. This also means that one needs to be very careful with updating or deleting rows using the View. Take a minute to think about how SQL compares to other programming languages like Java. What features are similar, and which are present in one language but not the other? The first and most clear difference is the syntax. SQL syntax is very different from that of Java and other programming languages. I think this makes basic SQL commands easy t...
Read more