Theory of Computation

Question 1

What name is given to the rules that define how symbols can be replaced by other symbols?

Answer 1

Production rules

Question 2

What type of object is enclosed in angle brackets in BNF?

Answer 2

Non-terminal

Question 3

Why can BNF represent some languages that regular expressions can’t?

Answer 3

BNF supports recursion & languages with counting

Question 4

What is the halting state in a Turing machine?

Answer 4

The state(s) with no outgoing transitions

Question 5

What is the starting state in a Turing machine?

Answer 5

The state that you start at

Question 6

What are the two states within a Turing machine?

Answer 6

Current state and next state

Question 7

Three components of a Turing machine?

Answer 7

• Infinite tape (in one direction)
• Read/write head
• Control unit

Question 8

What is the alphabet of a Turing machine?

Answer 8

1, 0 and blank.

Question 9

What makes a task computable?

Answer 9

If a Turing machine can complete it - every algorithm can be represented as a Turing Machine.

Question 10

What is a Universal Turing Machine?

Answer 10

A Turing Machine that faithfully executes operations exactly how the simulated Turing Machine would with the same process.

Question 11

What is the Halting problem?

Answer 11

The Halting problem is non-computable - no algorithm will solve it.

Question 12

What is a Heuristic?

Answer 12

It offers an approximate solution to intractable problems within polynomial times - not the most optimal solution.

Question 13

What is an intractable problem?

Answer 13

A problem that cannot be solved within polynomial time.

Question 14

What is the time complexity of an intractable problem?

Answer 14

a^n, n! or worse.

Question 15

What is a tractable problem?

Answer 15

A problem that can be solved in polynomial time or better.

Question 16

What is a computable problem?

Answer 16

A problem that can be solved with an algorithm - must always terminate and produce the correct output.

Question 17

What is a non-computable problem?

Answer 17

A problem in which no algorithm exists to solve the problem.

Question 18

What is Big-O notation?

Answer 18

A way of classifying algorithms by how their computation time grows as input size grows.

Question 19

What is the order of magnitude?

Answer 19

The term in the function that increases fastest (eg number w/ largest power)

Question 20

What is the time complexity of the linear search?

Answer 20

O(n)

Question 21

What is the time complexity of the bubble sort?

Answer 21

O(n^2)

Question 22

What is the time complexity of the merge sort?

Answer 22

O(nlogn)
- Linear logarithmic.

Question 23

What is the time complexity of the binary search?

Answer 23

O(logn)

Question 24

What do we assume with the time complexity of an algorithm?

Answer 24

Always assume the worst case scenario.

Question 25

What is the space complexity of an algorithm?

Answer 25

A measure of the amount of working storage space an algorithm needs.

Question 26

What is time complexity?

Answer 26

The amount of time it takes to run a program.

Question 27

What is automation?

Answer 27

Models being put into actions to solve real-life problems.

Question 28

What are the steps of automation?

Answer 28

- Creating algorithms - Implementing the algorithms in program code (instructions) - Implementing the models in data structures executing the code.

Question 29

What is psuedocode?

Answer 29

Code that can't be ran into a programming language, used to help a programmer lay out code without having to conform to the rules of a language.

Question 30

What is composition?

Answer 30

Combining procedures to form new compound procedures.

Question 31

What is decomposition?

Answer 31

Breaking down a problem into smaller, easier to solve sub-problems.

Question 32

What are the two main types (not only types) of abstraction?

Answer 32

Representational abstraction and abstraction by generalisation.

Question 33

What is abstraction by generalisation?

Answer 33

Grouping common characteristics in a hierarchical (is like) relationship.

Question 34

What is representational abstraction?

Answer 34

Filtering out unnecessary details.

Question 35

What is problem abstraction?

Answer 35

Simplifying into a problem into one that has already been solved and using that answer to solve the original problem.

Question 36

What is information hiding?

Answer 36

Hiding the details that are non-essential characteristics.

Question 37

What is data abstraction?

Answer 37

The simplification of a body of data to a simplified whole.

Question 38

What is procedural abstraction?

Answer 38

Abstracting the values away from a computational procedure. Result = PROCEDURE

Question 39

What is functional abstraction?

Answer 39

Identifying and representing a task with reusable functions/procedures.

Question 40

What is an algorithm?

Answer 40

A set of instructions to follow to perform a different task.

Question 41

REGEX: What is ?

Answer 41

Zero or one instances of the character (optional)

Question 42

REGEX: What is *?

Answer 42

Zero or more instances of the character

Question 43

REGEX: What is +?

Answer 43

One or more instances of the character

Question 44

REGEX: What is |?

Answer 44

Or