Computational Thinking

Question 1

What is representational abstraction?

Answer 1

The process of removing unnecessary details until its possible to represent the problem in a way that it can be solved

Question 2

What is abstraction by generalisation?

Answer 2

The process of placing aspects of the problem into broader categories to arrive at a hierarchical representation

Question 3

What is procedural abstraction?

Answer 3

The concept that solutions can be broken down into a series of subroutines or procedures
All of which can be solved individually and can be further broken down

Question 4

What is functional abstraction?

Answer 4

Abstracting a procedure into a group of common functions

Question 5

What is problem abstraction?

Answer 5

The process of reducing a problem down into its simplex components until the underlying processing requirements that solve the problems are identified.

Question 6

What is information hiding?

Answer 6

The process of providing a definition or interface of a system whilst hiding the inner workings (e.g. GUI hides the complexity of a program)

Question 7

What is decomposition?

Answer 7

The process of breaking large complex tasks into smaller, more manageable tasks

Question 8

What is composition?

Answer 8

Creating a working system from the smaller processes

Question 9

What is automation?

Answer 9

Creating computer models of real life situations and putting them into action
(e.g. Computer Model that models the profits of a coffee shop)

Question 10

What is a set?

Answer 10

A data type which contains unordered, unique values

Question 11

What is the cardinality of a set?

Answer 11

The number of elements within a set (only in finite sets)

Question 12

What is a subset?

Answer 12

A set which contains items from another set, but not every item from the other set

Symbol: ⊆

Question 13

Membership of a set symbols:

Answer 13

In a set: ∈
Not in a set: ∉

Question 14

What is a union? (combining sets)

Answer 14

Elements in A OR B
Set A ∪ Set B

Question 15

What is an intersection? (Combining Sets)

Answer 15

Elements in A and B
Set A ∩ Set B

Question 16

What is a difference? (Combining Sets)

Answer 16

A set which contains items exclusive to one set
A NOT B
B NOT A

A\B = {x : x ∈ A and x ∉ B}.

Question 17

What does the * represent? (Regular Expressions)

Answer 17

• Means 0 or more repetitions
  ab* = {a, ab, abb, abbb, …}

Question 18

What does the + represent? (Regular Expressions)

Answer 18

+ Means 1 or more repetitions
a+b = {ab, aab, aaab, …}

Question 19

What does the ? represent? (Regular Expressions)

Answer 19

? means that the previous character is optional
a?b = {b, ab}

Question 20

What does | represent? (Regular Expressions)

Answer 20

means or
a|b = {a, b}

Question 21

What does () represent? (Regular Expressions)

Answer 21

() is used to group regular expressions
(ab) | (cd) e = {abe, cde}

Question 22

What is Big O Notation?

Answer 22

Big O Notation describes the complexity of an algorithm, by assuming the worst case scenario.

Question 23

What is the order of complexity? (Least Complex to Most Complex)

Answer 23

Constant O(1)
Logarithmic O(logN) Binary Search
Linear - O(N) Linear Search
Linear Logarithmic - O(NLogN) Merge Sort
Polynomial - O(^2) Bubble Sort
Exponential - O(2^N) Recursively Counting Fibonacci Numbers
Factorial - O(N!) Travelers Problem

Question 24

What is an intractable problem?

Answer 24

A problem that is theoretically possible, but not within polynomial time
(e.g. Factorial or Exponential)

Question 25

What is a heuristic algorithm?

Answer 25

An algorithm which doesn’t give a fully accurate answer, but one with an approximate solution within a polynomial time

Question 26

What is the halting problem?

Answer 26

An unsolvable problem - it is impossible to write an algorithm to determine if another algorithm will finish giving a particular input. Therefore it isn’t possible to create a turing machine to solve it

Question 27

What is a Universal Machine?

Answer 27

A turing machine which can simulate the behaviour of any other Turing Machine by reading the description of the turing machine and faithfully executing operations on data
Acts as an interpeter as they can read their instructions in sequence before faithfully executing instructions on their input data.

Question 28

Why are Turing Machines useful?

Answer 28

They provide a definition of what is computable, meaning they can prove that there are problems which cannot be solved by computers - such as the halting problem

Question 29

What is a turing machine?

Answer 29

A formal model of computation which consists of a finite state machine, a read/write head and also a tape which is infinitely long
It is viewed as a computer which runs a single program

Question 30

Why is a Universal Machine deemed more powerful than a regular computer?

Answer 30

Contains an infinite read/write head - therefore infinite memory

Question 31

State the relationship between an algorithm and a turing machine

Answer 31

A turing machine can only be designed to solve a problem if an algorithm already exists for the problem

Question 32

Why is a UTM considered an interpreter?

Answer 32

Reads instructions line by line and executes them