Theory of Computation

Question 1

What is Abstraction?

Answer 1

Process of filtering out the details we don’t need in order to concentrate on those that we do – removing unnecessary details

Question 2

Define Representational Abstraction.

Answer 2

Removing unnecessary details

Question 3

What is abstraction by Generalisation?

Answer 3

Grouping by common characteristics to get a hierarchical relationship

Question 4

What is information hiding?

Answer 4

The process of hiding all details of an object that do not contribute to its essential characteristics

Question 5

What is procedural abstraction?

Answer 5

Breaking down a complex model into a series of reusable procedures; finds the generic method.

E.g.
(4*3) + 7 becomes
ab + c

Question 6

What is functional abstraction?

Answer 6

Procedural abstraction results in a procedure. Abstracting further disregards the method of a procedure and results in just a function which takes inputs and produces a specific output.

Question 7

What is Data Abstraction?

Answer 7

The reduction of a particular body of data to a simplified representation of the whole. For example, a stack could be implemented as an array and a pointer for the top of the stack.​

Question 8

What is Automation?

Answer 8

Process of putting abstractions of models into action to solve problems

Question 9

What is Decomposition?

Answer 9

Process of breaking down a complex problem into parts that are easier to understand

Question 10

What is Procedural Decomposition?

Answer 10

Breaking a problem down into smaller sub-problems

Each of which solves an identifiable task

Each of which might be further split up

Question 11

What is Complexity of a linear search?

Answer 11

O(n)

As the size of the list increases, time taken increases at the same rate
‘n’ is worst case

Question 12

What is the complexity of a binary search?

Answer 12

O(log n)

As time taken increases the size increase, but by less and less each time
Halves tree/graph each time

Question 13

What is meant by the time complexity of an algorithm? ign

Answer 13

The number of clock cycles taken for the CPU to execute the algorithm

Expressed using ‘big O notation’

Question 14

Describe the Halting Problem?

Answer 14

The unsolvable problem determining whether a program will halt, given a certain input, without running the given program.

Question 15

What is a Tractable Problem?

Answer 15

Problem that can be solved in an acceptable amount of time [polynomial time]

Question 16

What is an Intractable Problem?

Answer 16

Problem which cannot be resolved in polynomial time

Question 17

What is meant by the term Heuristic?

Answer 17

A method for producing a ‘rule of thumb’ to produce an acceptable solution to intractable problems

Better than n factorial

E.g,. Store your shortest path that you have so far and check another. Making approximation for the shortest path

Question 18

How to identify Polynomial?

Answer 18

Nested loops are always polynomial

Question 19

How to identify a Logarithmic Algorithm?

Answer 19

Halves the number of items each term

Question 20

What is meant by the term ‘Intractable Complexities’?

Answer 20

Ones more complex than polynomial

Question 21

State the Complexity Rules.

Answer 21

Remove all terms except one with largest factor/exponents

Remove any constants

3n^2 + 4n + 2 =
3n^2 =
n^2 =
O(n^2)

Question 22

Order of Algorithm Complexities:

Answer 22

Constant – O(c)

Logarithmic O( log(n) )

Linear O(n)

Linear Logarithmic O(n log(n) )

Polynomial O(n^2)

Exponential O(2^n)

Factorial O(n!)

Charlie Loves Licking Luscious Penis Every Friday !

Question 23

What does a Turing Machine consist of?

Answer 23

A finite state machine

A set of transition rules

A sensing read/write head

Start state

Set of accepting/ halting states

A tape that is infinitely long in one direction

State register/Current register

The finite alphabet of symbols that it can use

Question 24

Explain what a Universal Turing machine is

Answer 24

Turing machine that can simulate the behaviour of any other Turing machine

Faithfully executes operations on the data precisely as the simulated Turing Machine does

Acts as an interpreter

Question 25

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

Answer 25

There is no algorithm that solves the Halting Problem

Question 26

Why is a universal Turing machine more powerful than any other computer?

Answer 26

It has infinite tape

Question 27

What type of object is enclosed in angle brackets in Backus-Naur Form?

Answer 27

Non-Terminal

Question 28

What name is given to an object in Backus-Naur form that can’t be broken down any further?

Answer 28

Terminal

Question 29

In Finite State Machine what is the double circle?

Answer 29

Valid halting state

When it is valid to stop

Question 30

How does a finite state machine differ from a Turing machine?

Answer 30

Don’t have to worry about tape

Or header

Question 31

What is meant by the term reject state?

Answer 31

No escape from that state -no way out

Rule won’t be valid if you stop there

Question 32

What are finite state machines used for?

Answer 32

Used to validate an input

Represent regular expressions in a computer

A less powerful Turing machine

Question 33

What is a heuristic algorithm?

Answer 33

An algorithm that makes a guess/estimate based on experience

Used to tackle intractable problems.

Question 34

What’s the relationship between a Turing machine and an Algorithm?

Answer 34

A Turing Machine can compute any algorithm.

Question 35

What’s the purpose of a Turing Machine?

Answer 35

To provide a theoretical model which helps us understand how computers solve problems step by step.

Question 36

What is the time complexity of a merge sort?

Answer 36

O(nlogn)

The log(n) comes from dividing each array into halves
Then the (n) comes from sorting them by merging

Question 37

What is meant by the ‘cartesian product of two sets’ ?

Answer 37

Two sets A and B, written AB, is the set of all ordered pairs (a,b) where a is a member of A and b is a member of B.
e.g.,
A= {1,3,5} B ={ 12,25,40 } Set C is defined as AB
C = {(1,12), (1,25), (1,40), (3,12), (3,25), (3,40), (5,12), (5,25), (5,40)}

Question 38

What is the time complexity of a bubble sort?

Answer 38

O(n^2)
Nested Forloop

Question 39

What is an example of an algorithm with a Factorial time complexity?

Answer 39

Travelling Salesman

Question 40

What is Problem abstraction​?

Answer 40

Removing details from a problem until it can be represented in a way that is possible to solve because the problem reduces to one that has already been solved.”

Question 41

What is a finite state machine?

Answer 41

A computing machine that has a fixed set of possible states, a set of inputs that change the state and a set of possible outputs.

Question 42

Transition function format

Answer 42

δ(Current State, Input) = (Next State, Output, Movement Dir)

Question 43

Symbol for Integers

Answer 43

Z

Question 44

What is meant by a Proper Subset?

Answer 44

⊂
A subset is made up entirely of elements of another set but there is at least one element in the original set not included in this set.

Question 45

What is meant by a subset?

Answer 45

⊆
The subset can contain ALL the elements of the other set