Work through the list without notes. If you cannot do a statement, follow the pointer, then come back. Guide = the study guide; Practice = the practice questions.
Understanding
- I can distinguish a problem from an instance (Guide: Problems, instances and kinds of problem; Practice: Question 5)
- I can distinguish decision problems from optimization problems (Guide: Problems, instances and kinds of problem; Practice: Question 4)
- I can define efficiency as resource use expressed as a function of input size (Guide: What efficiency means; Practice: Question 1)
- I can state which growth rates are reasonable and which are unreasonable (Guide: Reasonable and unreasonable time; Practice: Question 3)
Skills
- I can count how many times a statement executes in a single and a nested loop (Guide: What efficiency means; Practice: Questions 2 and 9)
- I can compare two algorithms by counting steps as n grows (Guide: Worked example 1; Practice: Question 9)
- I can work out how long an exponential algorithm takes at a given speed (Guide: Reasonable and unreasonable time; Practice: Question 10)
Reasoning
- I can predict the effect on work of doubling n for linear, square and exponential growth (Guide: What efficiency means; Practice: Questions 7 and 9)
- I can explain why a faster computer does not rescue an exponential algorithm (Guide: Reasonable and unreasonable time; Practice: Question 10)
- I can explain when a heuristic is appropriate and that it does not guarantee the best answer (Guide: Worked example 2; Practice: Question 6)
- I can explain why different correct algorithms can have different efficiencies (Guide: Worked example 1; Practice: Question 8)
- I can separate unreasonable running time from impossibility (Guide: Common misconceptions; Practice: Question 8)
When every line is secure, move on. The revision notes are here: revision notes.