Algorithms Flashcards
1
Q
Algorithms
A
set of steps for solving an instance of a particular problem type
2
Q
Computational desiredata
A
- correctness
- efficiency: run time, storage
3
Q
Search
A
look for first instance of particular value in collection
4
Q
Exact method
A
- calculate solution with guaranteed correctness
- brute force, divide and conquer
5
Q
Approximate
A
- estimate solution ideally with additional estimate of how close this is to exact solution
- simulation
- heuristic
6
Q
Brute force
A
- generate and test
- Assumptions: candidate answer easy to test, ordered, can be generated exhaustively
- Strategy: test candidate answer one by one until solution is found
e. g. linear search
7
Q
Divide and conquer
A
Strategy: solve smaller sub problem, extend sub solution to create solution of original problem
e.g. binary search, relates closely to recursion
8
Q
Simulation
A
- randomly simulate large number of data to predict overall trend
- use multiple runs to verify stability of answer
- used where it is possible to describe individual properties of a system, not to capture the interaction between them
e. g. weather forecast
9
Q
Heuristic
A
- search via cheap, approximate solution which works reasonably well most of the time but there is not proof of how close to optimal the proposed solution is
e. g. play lower valid card every play
