2019 p1 Flashcards
‘Sorting a list becomes an intractable problem when the size of the list is very
large; it is a tractable problem when the size of the list is small.’
Explain why this statement is wrong.
sorting a list is always a tractable problem
A problem does not change from being tractable to intractable
Explain what approach(es) a programmer might take if asked to ‘solve’ an
intractable problem.
Use of heuristic
An algorithm that makes a guess
Explain what approach(es) a programmer might take if asked to ‘solve’ an
intractable problem.
Use of heuristic
An algorithm that makes a guess
Explain what a Universal Turing machine is
A Turing machine that can execute
representational abstraction
removing details
abstraction by generalisation
Grouping by common characteristics
Explain the circumstances when it would be more appropriate to use an adjacency
matrix instead of an adjacency list
when there are many edges between vertices
when edges frequently changed
Explain the functionality of the * metacharacter when it is used in a
regular expression
Zero or more
Explain the functionality of the ? metacharacter when it is used in a regular
expression.
Zero or one