2019 p1 Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

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

A

sorting a list is always a tractable problem

A problem does not change from being tractable to intractable

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

Use of heuristic
An algorithm that makes a guess

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

Use of heuristic
An algorithm that makes a guess

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Explain what a Universal Turing machine is

A

A Turing machine that can execute

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

representational abstraction

A

removing details

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

abstraction by generalisation

A

Grouping by common characteristics

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

when there are many edges between vertices
when edges frequently changed

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

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

A

Zero or more

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

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

A

Zero or one

How well did you know this?
1
Not at all
2
3
4
5
Perfectly