(4) Computation

Question 1

What does the Regular expression ‘a | b ‘ mean?

Answer 1

Any string that contains a or b

Question 2

What does the Regular expression ‘abb?’ mean?

Answer 2

The ? indicates that there is zero or one of the char right next to ?

E.g. abb or ab

Question 3

What does the Regular expression ‘ a+ ‘ mean?

Answer 3

Any string that contains one or more a

Question 4

What does the Regular expression ‘ a* ‘ mean?

Answer 4

Any string that consists of zero or more a’s

Question 5

What does the Regular expression ‘ ab ‘ mean?

Answer 5

Any string that contains an ‘a’ followed by ‘b’

Question 6

What does the Regular expression ‘ a ‘ mean?

Answer 6

Any string that contains a single ‘a’

Question 7

What are the two measures of efficiency?

Answer 7

• Time required to solve the problem

- Memory space required to solve the problem

Question 8

What does the following Big O notations mean and rank them from best to worst?: O(n) ,O(1) , O(2^n) , O(n^2), O(log n)

Answer 8

O(1): Constant complexity - BEST
O(log n): Logarithm complexity - GOOD
O(n): Linear complexity - DECENT
O(n^2) : Quadratic complexity - POOR
O(2^n): Exponential complexity - WORST

Question 9

What is Regular Expression?

Answer 9

A notation that determines when a string is valid without listing all valid strings

Question 10

What is a Set?

Answer 10

-An unordered collection of values where each value occurs once.

Question 11

What is Universal Turing Machine?

Answer 11

A Turing machine that can execute the behaviour of any other Turing
machine // can compute any computable sequence

Question 12

What is an algorithm?

Answer 12

A step-by-step description of how to complete a task for solving a problem

Question 13

What is information hiding?

Answer 13

The process of hiding the complexities of a program from the end user

Question 14

Why can the turning machine model can be used to recognise a greater range of languages then an FSA?

Answer 14

Because the turning machine has unlimited memory

Question 15

Why is the Turning Machine more powerful than the Finite State Automation (FSA)

Answer 15

Can be used to recognise a greater range of languages as it has unlimited memory

Question 16

What is a tractable problem?

Answer 16

A problem that is solvable within a reasonable amount of time on a computer

Question 17

What is a intractable problem?

Answer 17

A problem that is solvable but takes an unreasonable amount of time

Question 18

What can a programmer do to ‘solve’ an intractable problem?

Answer 18

An algorithm could make an educated guess based on previous data

Question 19

How can a Universal Turning machine be considered as a interpreter?

Answer 19

It reads instructions one at a time and executes the instructions

Question 20

What is representational abstraction?

Answer 20

Removing (unnecessary) details;

Question 21

What is abstraction by generalisation?

Answer 21

Grouping by common characteristics // a hierarchical / ‘kind-of’ relationship;

Question 22

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

Answer 22

Adjacency matrix appropriate when there are many edges between vertices

When graph/matrix is not sparse;
When edges frequently changed;
When presence/absence of specific edges needs to be tested frequently;

Question 23

What is BNF (Backus-Naur Form)?

Answer 23

A formal mathematical way of defining syntax unambiguously

Question 24

Describe the relationship between regular expressions and FSMs.

Answer 24

Regular language can be defined as any language that a FSM will accept