Topic study hub
Classification of algorithms
Official AQA 7517 section 4.4.4.
0
Objectives
10
Flashcards
10
Questions
90 min
Study time
AqaA LevelComputer ScienceTheory of computation
Choose a revision tool
Start revising Classification of algorithms
Syllabus checklist
What you need to know
0 objective pages available
Comparing algorithms1 objectives
- Comparing algorithms: Understand that algorithms can be compared by expressing their complexity as a function relative to the size of the problem. Understand that the size of the problem is the key issue. Understand that some algorithms are more efficient: • time-wise than other algorithms • space-wise than other algorithms. Efficiently implementing automated abstractions means designing data models and algorithms to run quickly while taking up the minimal amount of resources such as memory.
Maths for understanding Big-0 notation1 objectives
- Maths for understanding Big-0 notation: Be familiar with the mathematical concept of a function as a mapping from one set of values, the domain, to another set of values, drawn from the co-domain, for example ℕ → ℕ. 60 Be familiar with the concept of: • a linear function, for example y = 2x • a polynomial function, for example y = 2x 2 • an exponential function, for example y = 2x • a logarithmic function, for example y = log10 x. Be familiar with the notion of permutation of a set of objects or values, for example, the letters of a word and that the number of permutations of n distinct objects is n factorial (n!). n! is the product of all positive integers less than or equal to n.
Order of complexity1 objectives
- Order of complexity: Be familiar with Big-O notation to express time complexity and be able to apply it to cases where the running time requirements of the algorithm grow in: • constant time • logarithmic time • linear time • polynomial time • exponential time. Be able to derive the time complexity of an algorithm.
Limits of computation1 objectives
- Limits of computation: Be aware that algorithmic complexity and hardware impose limits on what can be computed.
Classification of algorithmic problems1 objectives
- Classification of algorithmic problems: Know that algorithms may be classified as being either: • tractable - problems that have a polynomial (or less) time solution are called tractable problems. • intractable - problems that have no polynomial (or less) time solution are called intractable problems. Heuristic methods are often used when tackling intractable problems.
Computable and non-computable problems1 objectives
- Computable and non-computable problems: Be aware that some problems cannot be solved algorithmically.
Halting problem1 objectives
- Halting problem: Describe the Halting problem (but not prove it), that is the unsolvable problem of determining whether any program will eventually stop if given particular input. Understand the significance of the Halting problem for computation. The Halting problem demonstrates that there are some problems that cannot be solved by a computer.
Key terms
Problem sizeSpace efficiencyDomainPermutationBig-O notationTime complexityAlgorithmic complexityHardware limitTractableIntractableComputable problemNon-computable problem
Exam tips
- Compare against problem size: When explaining algorithm efficiency, always state how time or memory use changes as the problem size increases.
- Read function notation carefully: For a notation such as ℕ → ℕ, identify the first set as the domain and the second set as the co-domain before describing the mapping.
Common mistakes
- Assuming fewer lines means greater efficiency: Compare how the algorithm's time and space requirements change relative to the problem size. Code length alone does not establish efficiency.
- Confusing exponential and polynomial functions: In y = 2x², x is raised to a power, so it is polynomial. In y = 2ˣ, x is the exponent, so it is exponential.
Practice preview
Continue by objective
Objectives are grouped by subtopic so students can jump straight to the exact skill they want to revise.
Related topics