Algorithmic approaches Flashcards
What is Brute force?
A straightforward approach to solving a problem (Usually the first solution)
Advantages of Brute Force
Conceptually simple
Usually the easiest strategy to apply
What is an algorithmic design strategy?
A general approach to
solving problems algorithmically that is applicable to a
variety of problems from different areas of computing
What is Divide & Conquer
A problem is divided into several subproblems. The subproblems are then solved (typically recursively), and combined to get the solution to the original problem.
What is a Greedy Algorithm?
At every step, make the best move you can make (locally optimal choice) until you’re done.
What’s an advantage of Greedy Algorithms?
▶ Not effort at each step
▶ Usually finds a solution very quickly
▶ The solution found is usually not bad
What’s a disadvantage of Greedy Algorithms?
▶ The solution found may NOT be the best one
What is iterative improvement?
Starting from some initial feasible solution , the algorithm proceeds to improve it by repeated applications of some simple step
Potential problems of Iterative improvement
Hard to identify an initial feasible solution.
Difficult to identify if a locally optimal next step will yield a globally optimal solution to a problem.
What is Dynamic programming?
It solves every sub-subproblem just
once and then saves its answer in a table (or array).
This avoids the work of recomputing the answer every time the sub-subproblem is encountered.
