Heuristics and Dynamic Programming (DP) Flashcards
What are the four different paradigms for finding solutions to problems?
Brute Force
Divide-and-Conquer
Heuristics
Dynamic Programming
What is Brute Force?
Generate and test all possibilities
Useful in small cases, but gets very quickly out of hand for larger cases
What is Divide-And-Conquer?
Break the problem into smaller pieces, solve them, and then put them back together e.g. Merge Sort
What is a heuristic?
Generally, meant to mean something that gives better decisions, than the naive methods, but still not necessarily optimal
Two types:
Decisions within a procedure that give exact/optimal answers, but are designed to make it go faster
Decisions within a procedure that might not give optimal answers, but are designed to give good answers that are impractical to obtain otherwise
What are heuristics in exact methods?
General methods that work in an algorithm that does give exact or optimal answers, but need the heuristic to decrease the average/typical runtime
What are heuristics in inexact methods?
Generally methods that are not guaranteed to give the best possible answers, but that can give good answers quickly
Used on problems when the exact methods are too slow
What is a greedy algorithm?
Take the decision that looks best in the short term, without looking ahead
How does the greedy algorithm work on the change-giving problem?
Iterate the process of picking the largest coin which is still available and does not cause the set to exceed the target
What is dynamic programming?
Solve small sub-problems first, then build up towards the full solution
How does DP work for Subset Sum?
Consider the numbers one at a time, keeping track of ‘which subset sums are possible so far’
What is the complexity of DP?
Outer loop - O(n)
Inner loop - O(k)
Overall - O(n K) (also written as O(n 2^B)
