Fundamentals of Computational Thinking

Question 1

Define Automation

Answer 1

Creating a computer model of a real-life situation and putting it into action

Question 2

Define Logical reasoning

Answer 2

the process of using a given set of facts to determine whether new facts are true or false.

Question 3

Define representational abstraction

Answer 3

The process of removing unnecessary details so that only information that is required to solve the problem remains.

Question 4

Define the term Algorithm

Answer 4

A sequence of instrucutions to achieve a specific outcome in a finite time.

Question 5

Define decomopsition

Answer 5

Breaking down a large task into a series of subtasks

Question 6

Define composition

Answer 6

Building up a whole system from smaller units. (Opposite of decomposition)

Question 7

What is a Finite State Machine? (FSM)

Answer 7

Any device that stores its current status and whose status can change as the result of an input. (Mainly used as a conceptual model for designing and describing systems.)

Question 8

What is a state transition diagram

Answer 8

A visual representation of a FSM using circles and arrows.
Single circle = state
Arrow = input
Double circle = Accepting state or final state

Question 9

What is a state transition table.

Answer 9

A tabular representation of a FSM showing:

Inputs, Current State and Next State (3 columns)

Question 10

Define the term Mealy Machine

Answer 10

This is a finite state machine with outputs

Question 11

What is a Turing Machine

Answer 11

A theoretical model of computation

Question 12

Define the term Alphabet in terms of a Turing Machine

Answer 12

The acceptable symbols, charactor and/or numbers for a given Turing Machine

Question 13

What is a read/write head?

Answer 13

The theoretical device that writes or reads from the current cell of a tape in a Turing machine.

Question 14

What is a halting state?

Answer 14

A state that, when reached, stops the Turing machine

Question 15

What is a regular expression?

Answer 15

Notation that contains strings of characters that can be matched to the contents of a set.

Question 16

Define the term regular language

Answer 16

Any language that can be described using regular expressions

Question 17

What does a + mean in a regular expression?

Answer 17

One more more of the previous statement

Question 18

What does a ? mean in a regular expression?

Answer 18

Either zero or one of the previous statement

Question 19

What does a | mean in a regular expression?

Answer 19

The previous statement or the next statement

Question 20

What does a * mean in a regular expression?

Answer 20

Zero or more of the previous statement

Question 21

Therefore what is the meaning of this statement?

(a|b)c

Answer 21

a or b and c

Question 22

What does {x, y} mean in a regular expression where x and y are different integers?

Answer 22

The previous statement at least x times, but no more than y times (therefore it is inclusive of those numbers)

Question 23

What is a function defined as in Big O notation?

Answer 23

It relates each element of a set with the element of another set. E.g. f(x) = 2x

Question 24

What is the domain?

Answer 24

All the values that may be input to a mathmatical function.

Question 25

What is the codomain? (range in Maths)

Answer 25

All the values that may be output from a mathmatical function.

Question 26

Big O notation describes two complexities of an algorithm. What are they?

Answer 26

1) Time complexity - how much time an algorithm requires to complete
2) Space complexity - how much space an algorithm requires to complete

Question 27

What does the notation O(1) represent?

Answer 27

Constant time - where the time taken to run an algorithm does not vary with the input size.

Question 28

What does the notation O(N) represent?

Answer 28

Linear Time - where the time taken to run an algorithm increases in direct proportion to the input size

Question 29

What does the notation O(N^2) represent?

Answer 29

Polynomial time - where the time taken to run an algorithm increases in proportion to the square of the input size

Question 30

What does the notation O(2^N) represent?

Answer 30

Exponential time - where the time taken to run an algorithm increases as an exponential function of the number of inputs.

E.g. for each additional input the time taken might double.

THIS IS BAD!

Question 31

What does the notation O(logN) represent?

Answer 31

Logarithmic time - where the time taken to run an algorithm increased or decreases in line with a logarithm.

Question 32

What is the order of efficiency of all 5 of the Big O notations?

Answer 32

1) O(1) or Constant Time
2) O(logN) or Logarithmic Time
3) O(N) or Linear Time
4) O(N^2) or Polynomial Time
5) O(2^N) or Exponential Time

Question 33

What is a tractable problem?

Answer 33

A problem that can be solved in an acceptable amount of time.

Question 34

What is an intractable problem?

Answer 34

A problem that cannot be solved within an acceptable time frame.

Question 35

Define the term Heuristic.

Answer 35

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

Question 36

What is a Halting Problem?

Answer 36

An example of an unsolvable problem where it is impossible to write a program that can work out whether another problem will halt given a particular input.