CST-370 Week 3
This week, I learned multiple algorithms that apply different techniques to solving problems. They include Brute force and Divide-and-Conquer.
Brute-force String Matching
Given a string of n characters, text, and a string of m characters called the pattern, find a substring of the text that matches the pattern.
Basic idea for solving string problems with Brute Force
- 1. Character by character comparison
- 2. If a mismatch occurs, shift a character and restart the comparison
Efficiency for best case: If there is an immediate match, minimum number of comparisons will occur. (m)
E.g.
- Text: CSUMBGO
- Pattern: CSU
Efficiency for worst case: If there is no matching pattern, may iterate through entire text.
Exhaustive Search and TSP
Exhaustive search: A brute-force approach to solving combinatorial problems.
Basic idea:
1. Generate all potential solutions (or all possible cases) to the problems.
2. Evaluate each case one by one
3. Determine the solutions among the possible cases.
Traveling Salesman Problem (TSP): Used to find the shortest tour through a given set of n cities that visits each city exactly once before returning to the city where it started.
Time complexity of TSP:
1. Efficiency depends on the number of permutations
2. If there are n nodes in the question, we should identify all possible paths of the (n-1) node, except for the starting node.
- The total possible paths are:
(n-1)! = (n-1) * (n-2) * ... * 2 * 1
- Therefore, the time efficiency of the problem requires at least (n-1)!
Exhaustive Seach - Knapsack
Knapsack problem: A classic optimization problem. Given n items (wights, values), find the most valuable subset of the items that fit into a knapsack with the capacity W. (Only 1 quantity per item. Can't take the same item twice)
Example:
Knapsack capacity: 10 (i.e. W = 10)
- Item 1: w1 = 7, v1 = $42
- Item 2: w2 = 3, v2 = $12
- Item 3: w3 = 4, v3 = $40
- Item 4: w4 = 5, v4 = $25
Basic idea:
1. Consider all possible subsets.
2. Compute weight and value of each subset
3. Find the best subset which provides the maximum value
Best: {3, 4}
Time Efficiency: The number of possible subsets of a set with n items in 2^n, thus time complexity is at least 2^n
Depth-First Search (DFS)
A popular algorithm for graph traversal (and BFS). Processes all vertices and edges in a systematic way. (Graph traversal). DFS uses a "mark" array to indicate whether a vertex has already been visited or not. It uses a Stack for its operation. Time efficiency using Adjacency matric: n^2. Adjacency list: V + E
Applications of DFS:
1. Checking connectivity
2. Checking acyclicity of a graph
3. Finding connected components
Example:
Breadth-first Search (BFS)
BFS uses a "mark" array to indicate whether a vertex has already been visited or not. It uses a Queue for its operation. Unlike DFS, we put all the nodes that we can visit from the current node into the queue. Time efficiency using Adjacency matrix: V^2. List: V + E
Using BFS, we can find all paths from a vertex to all other vertices with the smallest number of edges.
Applications of BFS is same as DFS.
Divide and Conquer
Best-known problem-solving technique
1. A problem is divided into several subproblems. Typically, 2 subproblems
2. Subproblems are solved recursively until each subproblem is small enough to solve right away
3. If it's necessary, the subproblems are combined (or conquered) to get the solution of the original problem
To find the time efficiency of Divide and Conquer, we use the Master Theorem.
Master Theorem has 3 variables: a, b, and d
a: number of subproblems to be solved (# of recursive calls)
b: factor by which the input is reduced
d: exponent in θ(n^d), where θ(n^d) represents the time to divide the problems and/or combine the solutions for a problem of size n
Case 1: if a < b^d, then θ(n^d)
Case 2: if a = b^d, then θ(n^d*logn)
Case 3: if a > b^d, then θ(n^log_b(a))
In general, T(n) = aT(n/b) + f(n) where f(n) is an element of θ(n^d), d >= 0
Comments
Post a Comment