Fundamentals of Computational Thinking

Question 1

Decomposition

Answer 1

Breaking down a large task into a series of subtasks.

http://slideplayer.com/slide/9296226/28/images/29/Decomposition+/+Composition.jpg

Question 2

Composition

Answer 2

Building up a whole system from smaller units. This is the opposite of decomposition.

Question 3

Finite State Machine (FSM)

Answer 3

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

Finite - countable

State Transition Diagram - A visual representation of a FSM using circles and arrows.

Accepting State - The state that identifies whether an input has been accepted.

Question 4

State Transition Table

Answer 4

A tabular representation of an FSM showing inputs, current state and next state.
http://image.ibb.co/dsVUYJ/AFB6_B8_F0_9_E9_F_4409_9_A5_C_C1_F7_BC5_B8_E9_B.jpg

Question 5

Mealy Machine

Answer 5

A type of finite state machine with outputs

http://slideplayer.com/slide/8108911/25/images/11/Mealy+machine+0%C2%A2+Reset.+5%C2%A2+N/0.+N+++D/1.+10%C2%A2+D/0.+15%C2%A2+D/1.+symbolic+state+table..jpg

Question 6

Cipher

Answer 6

An algorithm that encrypts and decrypts data, also known as code.

Question 7

Shift Cipher

Answer 7

A simple substitution cipher where the letters are coded by moving a certain amount forwards or backwards in the alphabet.

Question 8

Turing Machine

Answer 8

A theoretical model of computation

Alphabet - the acceptable symbols (characters, numbers) for a given Turing Machine

Read/Write Head - the theoretical device that writes or reads from the current call of a tape in a Turing machine.

Halting State - Stops the Turing machine

Start State - The initial state of a Turing Machine

Instruction Table - A method of describing a Turing machine in tabular form.

https://www.youtube.com/watch?v=Ty57TncUSno

Question 9

Transition function/rule

Answer 9

A method of notating how a Turing machine moves from one state to another and how the data on the tape changes.

Question 10

Universal Machine

Answer 10

A machine that can simulate a Turing machine by reading a description of the machine along with the input of its own tape. This can solve the limitation of the Turing machine of requiring that every process will need to have its own Turing machine to do it.

Question 11

Regular Language

Answer 11

Any language that can be described using regular expressions.

Question 12

Regular Expression

Answer 12

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

Example:
a|b|c is a regular expression, which means that the set will contain either an ‘a’ or a ‘b’ or a ‘c’. A set is a collection of data that is unordered and contains each item at most once. It is written as follows showing the name of the set and the contents within brackets:
alphabet = {a, b, c, d, e, f, g, …}
integers = {0, 1, 2, 3, 4, 5, 6, 7, …}

Question 13

Common Regular Expressions

Answer 13

a|b|c means ‘a’ or ‘b’ or ‘c’

abc means ‘a’ and ‘b’ and ‘c’

a*bc means zero or more ‘a’ followed by ‘b’ and ‘c’

(a|b)c means ‘a’ or ‘b’ and ‘c’

a+bc means One or more ‘a’ and ‘b’ and ‘c’

ab?c means ‘a’ and either zero or one ‘b’ and ‘c’

Question 14

Context-free Language

Answer 14

An unambiguous way of describing the syntax of a language useful where the language is complex.

Question 15

Backus-Naur Form (BNF)

Answer 15

A form of notation for describing the syntax used by a programming language

https://www.youtube.com/watch?v=x1gGInKNCRw

Terminal - In BNF, it is the final element that required no further rules.

Question 16

Syntax Diagram

Answer 16

A method of visualising rules written in BNF or any other context-free language
https://www.google.ae/search?biw=1282&bih=1291&tbm=isch&sa=1&ei=Z1EUW_n5CsGKU-OespAB&q=syntax+diagram&oq=Syntax+dia&gs_l=img.3.0.35i39k1j0l2j0i30k1j0i5i30k1l5j0i8i30k1.1674655.1676091.0.1677263.9.9.0.0.0.0.223.1051.0j5j1.6.0….0…1c.1.64.img..3.6.1049…0i67k1.0.xbV0nqcvbMk#imgrc=jUPa6JDOzQELZM:

Question 17

Big O Notation

Answer 17

A method of describing the time and space complexity of an algorithm.

Space Complexity - The concept of how much space an algorithm requires.

Time Complexity - The concept of how much time an algorithm requires.

Input Size - In Big O Notation the size of what ever you are asking an algorithm to work with eg data, parameters.

Question 18

Constant Time O(1)

Answer 18

Means that the algorithm will always execute in exactly the same amount of time regardless of the input size.

Question 19

Linear Time O(N)

Answer 19

Means that the runtime of the algorithm will increase in direct proportion with the input size. (the more inputs, the longer it will take)

Question 20

Polynormial Function O(N^2)

Answer 20

Means that the runtime of the algorithm will increase proportionate to the square of the input size.

Iterative or nested statements such as bubble sorts and insertion sorts are examples of these as the program has to go back through itself again with each iteration.

Question 21

Exponential Time O(2^N)

Answer 21

Where the time taken to run an algorithm increases as an exponential function of the number of inputs.

Question 22

Logarithmic Time O(logN)

Answer 22

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

Question 23

Common Algorithms with Time Complexity in Big O Notation

Answer 23

O(1) - Indexing an Array
O(logN) - Binary Search
O(N) - Linear Search of an Array
O(N^2) - Bubble Sort
              Selection Sort
              Insertion Sort
              Nested Loops
O(2^N) - Interactable Problems

Question 24

Tractable Problem

Answer 24

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

Question 25

Intractable Problem

Answer 25

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

Question 26

Unsolvable Problem

Answer 26

A problem that has been proved cannot be solved on a computer

Question 27

Halting Problem

Answer 27

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.

Question 28

Finite Set*

Answer 28

A set where the elements can be counted using natural numbers up to a particular number

Question 29

Infinite Set

Answer 29

A set that is not finite

Question 30

Cardinality

Answer 30

The number of elements in a set

Question 31

Countable Set

Answer 31

A finite set where the elements can be counted using natural numbers.

Question 32

Countability infinite sets

Answer 32

Sets where the elements can be put into a one-to-one correspondence with the set of natural numbers.

Question 33

Cartesian Product

Answer 33

Combining the elements of two or more sets to create a set of ordered pairs