2019 p1

Question 1

‘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.

Answer 1

sorting a list is always a tractable problem

A problem does not change from being tractable to intractable

Question 2

Explain what approach(es) a programmer might take if asked to ‘solve’ an
intractable problem.

Answer 2

Use of heuristic
An algorithm that makes a guess

Question 2

Explain what approach(es) a programmer might take if asked to ‘solve’ an
intractable problem.

Answer 2

Use of heuristic
An algorithm that makes a guess

Question 3

Explain what a Universal Turing machine is

Answer 3

A Turing machine that can execute

Question 4

representational abstraction

Answer 4

removing details

Question 5

abstraction by generalisation

Answer 5

Grouping by common characteristics

Question 6

Explain the circumstances when it would be more appropriate to use an adjacency
matrix instead of an adjacency list

Answer 6

when there are many edges between vertices
when edges frequently changed

Question 7

Explain the functionality of the * metacharacter when it is used in a
regular expression

Answer 7

Zero or more

Question 8

Explain the functionality of the ? metacharacter when it is used in a regular
expression.

Answer 8

Zero or one