Learning objective
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.
Read the explanation, check the common trap, then practise with flashcards and questions.
At a glance
0
Flashcards
0
Questions
Topic
Classification of algorithms
Subtopic
Classification of algorithmic problems
Aqa A Level Computer ScienceTheory of computation
Study support
Understand this objective
Quick explanation
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
- This point belongs to Classification of algorithms, especially Classification of algorithmic problems.
- You need to be able to 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.
- Use the linked flashcards and practice questions to check recall, then practise applying the idea in an exam-style answer.
Why it matters
This objective helps connect Classification of algorithmic problems to exam-style questions, flashcards, and revision notes for Classification of algorithms.
Quick student answer
Which description best defines a tractable problem?
Direct answer
A problem with a polynomial (or less) time solution
Key terms
- Tractable: Describes a problem that has a polynomial (or less) time solution.
- Intractable: Describes a problem that has no polynomial (or less) time solution.
Common trap
Confusing intractable with impossible: State that an intractable problem has no polynomial (or less) time solution. Do not state that it has no solution of any kind.
Related questions
Try this as a practice card
Question 1 of 4
Choose an answer, get feedback, then move sideways through the set.
0 of 4 attempted
Flashcard prompts
Flip through the key recall cards
Flashcard 1 of 4
Press Space to flip, arrows to move
Revision tools
Choose how to practise
Flashcards0 linked cards
No objective-specific flashcards are cached for this page. Use the topic hub to revise the surrounding flashcards without triggering a frozen-subject DB fallback.Open topic hub
Practice Questions0 linked questions
No objective-specific practice questions are cached for this page. Use the topic question bank to practise nearby curriculum questions without weakening the egress guard.Open topic questions
Related learning 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.
Comparing algorithms
- 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.
Maths for understanding Big-0 notation
- 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.
Order of complexity
- Limits of computation: Be aware that algorithmic complexity and hardware impose limits on what can be computed.
Limits of computation
- Computable and non-computable problems: Be aware that some problems cannot be solved algorithmically.
Computable and non-computable problems