04 Theory of Computation

Question 1

Define algorithm.

Answer 1

A series of steps which can be followed to carry out a task and always terminates.

Question 2

Define representational abstraction.

Answer 2

Removing unnecessary detail to produce a simpler representation of the problem e.g. the London tube map - specific details about the lines are removed

Question 3

Define abstraction by generalisation.

Answer 3

Grouping objects in terms of shared characteristics to arrive at a hierarchical relationship of the ‘is a kind of’ type.
e.g. A Pomeranian is a breed of dogs; all dogs share the same characteristics of eyes, ears, 4 legs and a tail; cats also shared those characteristics; both dogs and cats fall under group of Carnivora which also include badgers, skunks and bears

Question 4

What is procedural abstraction?

Answer 4

Procedural abstraction represents a computational method by abstracting away the actual values used in any particular computation with general parameters to a procedure/function

Question 5

What is functional abstraction?

Answer 5

Where the implementation of the computational method is hidden like a black box which takes in set of inputs and produces an output
e.g. Python has built-in functions such as the math library which provides the value of pi or process to calculate the square root of a value

Question 6

Outline data abstraction.

Answer 6

Data abstraction is a technique that allows you to separate the way that a compound data object is used, from the details of how it is constructed.

e.g. The abstract concept of a stack, and its operations, can be understood without any consideration of how it is implemented

Question 7

What is problem abstraction/reduction?

Answer 7

Problem reduction is the process of generalising or reducing a problem to one that has already been solved

Question 8

Define decomposition.

Answer 8

Procedural decomposition means breaking a problem into a number of sub-problems, so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided.

Question 9

Outline automation.

Answer 9

Putting models (abstraction of real world objects/phenomena) into action to solve problems. This is achieved by:

• creating algorithms
• implementing the algorithms in program code (instructions)
• implementing the models in data structures
  executing the code.

Question 10

Outline what FSMs are.

Answer 10

Finite State Machine
An abstract representation of how something changes state in response to an event or condition

Question 11

Define a set.

Answer 11

A set is a well-defined collection of objects.
Objects of sets are members or elements
Sets can be unordered
Each member in a set can only occur once.
Set = upper case, member = lower case

Question 12

What are finite and infinite sets?

Answer 12

Finite set consists of a distinct number of members where number is a subset of N
Infinite set contains an endless number of distinct members

Question 13

Define a countably infinite set.

Answer 13

A set where its members can be counted using the infinite set of N

Question 14

How do you find the cardinality of a set?

Answer 14

The cardinality of a set is the number of members of the set
The cardinality of set A would be denoted as |A|

Question 15

How do you find the Cartesian product of a set?

Answer 15

The cardinality of sets A and B is the set of all ordered pairs (a, b) such that a ∈ A and b ∈ B and this is denoted as A X B.

Question 16

What is a subset and proper subset?

Answer 16

If A is a subset of B, every member of A is also a member of B.

If A is a proper subset of B, every member of A is also a member of B but A ≠ B.

Question 17

What are the four metacharacters in regular expressions?

Answer 17

• ‘*’ = 0 or more repetitions
• ’+’ = 1 or more repetitions
• ’?’ = 0 or 1 repetitions i.e. optional
• ’|’ = alternation/or

Question 18

Give example of Backus-Naur form.

Answer 18

<digit> ::= 0|1|2|3|4|5|6|7|8|9
</digit>

Question 19

Show recursion in Backus-Naur.

Answer 19

Used to define ‘one or more’ of a symbol

<number> ::= <digit>|<digit><number>
</number></digit></digit></number>

Question 20

What is time complexity?

Answer 20

Time complexity refers to the time it takes an algorithm to run in relation to the size of the input e.g. the computational time of an algorithm can increase dramatically when the amount of input data is doubled, while for a different algorithm the computational time can remain stable

Question 21

What is space complexity?

Answer 21

space complexity refers to the amount of memory required by an algorithm to solve a problem, depending on the size of the input.

e.g. how much more (if any) memory will the algorithm require if the input data is doubled?

Question 22

What is order of growth?

Answer 22

How an algorithm’s time and space complexity changes (increases, decreases, or remains stable) when the size of the input changes

Question 23

What are the time-complexities of known searching algorithms?

Answer 23

• Linear search = O(n)
• Binary Search = O(logn)
• Binary Tree search = O(logn)

Question 24

What are the time-complexities of the sorting algorithms?

Answer 24

• Quick sort = O (nlogn)
• Merge sort = O (nlogn)
• Bubble sort = O (n²)
• Insertion sort = O (n²)

Question 25

Explain what tractable and intractable problems are.

Answer 25

• Tractable means ‘manageable’, so the term is used to describe problems that are solvable in a reasonable time frame.
• A problem is defined as tractable if an algorithm exists to solve it that can be executed in polynomial time (or less).
• Problems that grow exponentially or factorially are said to be intractable. e.g. travelling salesman: (n - 1)!

Question 26

What are heuristic methods?

Answer 26

• Heuristic methods are used to tackle intractable problems.
• They return solutions that are are not entirely accurate, optimal, or complete, but are fit for purpose and achievable in a reasonable time frame
• e.g. in travelling salesman, instead of calculating all possible routes, selecting the nearest unvisited city - this finds a route in a feasible number of steps, but the solution is not necessarily the shortest path

Question 27

Describe the Halting problem.

Answer 27

• The Halting problem is the unsolvable problem of determining whether any program will eventually stop if given particular input
• The Halting problem demonstrates that there are some problems that cannot be solved by a computer.

Question 28

Describe the Turing machine.

Answer 28

A Turing machine can be described as a computer with a single fixed problem expressed using:
- a finite set of states in a state transition diagram
- a finite set of alphabet symbols
- an infinite tape with marked off squares
- a sensing read-write head that can travel along the tape one square at a time

One of the states is called a start state and states that have no outgoing transitions are called halting states.

Question 29

What is the syntax for a transition function in a state transition diagram.

Answer 29

δ (Current state, Input Symbol) = (Next state, Output Symbol, Head move)

Question 30

What is the importance of the Turing machine?

Answer 30

• Turing machines provide a (general/formal) model of computation and provide a definition of what is computable.
• The Universal Turing machine led to the idea of the stored program computer and von Neumann designed a computer which stores data and instructions in memory
• A computer based on von Neumann’s idea was developed in the 1940s and most computers today are still based on that design.