Algorithms

Question 1

Algorithms

Answer 1

set of steps for solving an instance of a particular problem type

Question 2

Computational desiredata

Answer 2

• correctness

- efficiency: run time, storage

Question 3

Search

Answer 3

look for first instance of particular value in collection

Question 4

Exact method

Answer 4

• calculate solution with guaranteed correctness

- brute force, divide and conquer

Question 5

Approximate

Answer 5

• estimate solution ideally with additional estimate of how close this is to exact solution
• simulation
• heuristic

Question 6

Brute force

Answer 6

• 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

Question 7

Divide and conquer

Answer 7

Strategy: solve smaller sub problem, extend sub solution to create solution of original problem
e.g. binary search, relates closely to recursion

Question 8

Simulation

Answer 8

• 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

Question 9

Heuristic

Answer 9

• 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