click below
click below
Normal Size Small Size show me how
Algorithmic Strategy
CMSC 132
Term | Definition |
---|---|
Recursive | A function that class itself one or more times by breaking it down into smaller sub-problems. (Calculating the factorial of a number) |
Backtracking | Depth first recursive search. Incrementally builds candidates to the solutions of a problem and abandons a candidate as soon as it determines that the candidate cannot possibly be completed to a valid solution. Search tree |
Divide and Conquer | The problem is divided into smaller subproblems that can be solved independently, and then the solutions are combined to produce a solution to the original problem. (Quicksort, MergeSort) |
Dynamic | technique for solving problems by breaking them down into smaller subproblems and solving each subproblem only once. It involves storing the solutions to subproblems so that they can be reused later. (Calculating the nth Fibonacci numberer or Dijkstras) |
Greedy | The solution is constructed incrementally by making a series of choices that are locally optimal at each step. The hope is that the locally optimal solution will lead to a global optimal solution (kind of Dijkstras) |
Brute Force | All possible solutions to a problem are generated and the best solution is selected. These are impractical for large input sizes(Searching for a substring in a string by checking every possible solution) |
Branch and Bound | It involves recursively partitioning the solution space into smaller subproblems and keeping track of the best solutions found so far. The algorithm stops when it can be shown that the best possible solution is worse than the current best solution. (TSP) |
Heuristic | Rule of thumb or good enough solution. Often used in situations where finding an exact solution is computationally infeasible or too time consuming (next nearest neighbor algorithm for the traveling salesman problem) |