4 - Theory of Computation

Question 1

What does the term algorithm mean?

Answer 1

An algorithm is a sequence of steps that can be followed to complete a task and that can be completed in finite time.

Question 2

What does a double circle indicate in a FSA?

Answer 2

Accepting state.

Question 3

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

Answer 3

Zero or more of the preceding value.

Question 4

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

Answer 4

Zero or one of the preceding value.

Question 5

Describe the significance of the Halting problem for commutation.

Answer 5

The Halting problem demonstrates that there are some problems that cannot be solved by a computer.

Question 6

What is the question posed by the by the Halting problem?

Answer 6

Is it possible in general to write a program that can tell, given any program and its inputs, and without running the program, whether the given program with its given inputs will halt?

Question 7

Why is it not possible to create a Turing machine that solves the Halting problem?

Answer 7

The Halting problem is non-computable

Question 8

What is a finite state machine?

Answer 8

It is a model of computation

Question 9

What is a Turing machine

Answer 9

A hypothetical machine capable of solving any problem that can be represented algorithmically

Question 10

What does a Turing machine define

Answer 10

defines the limits of computers

Question 11

What are the components of a Turing machine. (5)

Answer 11

An infinitely long tape divided into squares/ finite alphabet of symbols/ A read/write head/ finite set of states and a set of transition rules

Question 12

What does “|” mean in a finite state machine

Answer 12

Acts as a break point to show input on the left out put on the right

Question 13

What is the Universal Turning Machine

Answer 13

A Turing machine that can execute other Turing machines by stimulating their behavior.

Question 14

What are the two parts of the Turing machine instruction

Answer 14

Data and standard description

Question 15

What is the standard description of a turing machine

Answer 15

describes the turing machine that is being inputted allowing the UTM to accurately interpret the turing machine

Question 16

what is a regular expression?

Answer 16

A compact notation that can describe a set of strings that make up a regular language.

Question 17

What is the significance of a Universal Turing machine to the theory of computation?

Answer 17

it is possible for a single machine to compute anything that is computable.

Question 18

What 2 ways can we measure complexity

Answer 18

time complexity/ space complecity

Question 19

Why is time complexity important

Answer 19

allows us to measure efficiency of algorithm runtime.

Question 20

Why is space complexity important

Answer 20

allows us to measure the usage of resources by the computer by any given algorithm.

Question 21

What is meant by the worst case

Answer 21

The maximum amount of time that an algorithm can run for before reaching its answer

Question 22

What is meant by the best case

Answer 22

Time taken for only one iteration of the algorithm to execute.

Question 23

What is meant by the average case

Answer 23

mean number of computational time taken.

Question 24

What is Big O notation?

Answer 24

a formal expression of an algorithm’s complexity in relation to growth of the input size

Question 25

What is the classification for this Big O expression: O(1)

Answer 25

Constant time

Question 26

What is the classification for this Big O expression: O(log n)

Answer 26

Logarithmic time

Question 27

What is the classification for this Big O expression: O(n)

Answer 27

Linear Time

Question 28

What is the classification for this Big O expression: O(n^2)

Answer 28

Polynomial time

Question 29

What is the classification for this Big O expression: O(2^n)

Answer 29

Exponential time

Question 30

What is the classification for this Big O expression: O(n!)

Answer 30

Factorial time

Question 31

What is the basic operation of an algorithm

Answer 31

operation contributing most to the total running time/ most executed line of code

Question 32

What is the dominant term

Answer 32

part of the time complexity of a problem will dominate over the other parts

Question 33

What is a permutation

Answer 33

a set of objects is the number of different ways to arrange them when order matters.

Question 34

What is a tractable problem

Answer 34

A problem with a polynomial-time solution

Question 35

What is an intractable problem

Answer 35

A problem that can be solved, but does not have a polynomial-time solution

Question 36

What is a heuristic algorithm

Answer 36

they return solutions that are are not entirely accurate/ optimal/ or complete/ but are fit for purpose and achievable in a reasonable time frame.

Question 37

What is the halting problem

Answer 37

‘Is it possible to write a program that can tell given any program and its inputs and without executing the program/ whether it will halt?’

Question 38

Why is the halting problem significant?

Answer 38

It proves that there are problems that cannot be solved computationally.

Question 39

In regular expressions what does this mean: a*

Answer 39

zero or more “a”s

Question 40

In regular expressions what does this mean: a?b?

Answer 40

0 or 1 “a”s followed by 0 or 1 “b”s

Question 41

In regular expressions what does this mean: a+[ba]*

Answer 41

1 or more “a”s followed by zero or more of either “b” or “a”

Question 42

In regular expressions what does this mean: \d

Answer 42

matches any digit [0-9]

Question 43

In regular expressions what does this mean: \D

Answer 43

matches any digit that is not [0-9]

Question 44

In regular expressions what does this mean: \w

Answer 44

matches any word

Question 45

In regular expressions what does this mean:\W

Answer 45

Matches any non words

Question 46

What is a regular language

Answer 46

A language that can be represented by a regular expression and will be accepted by a FSM