Computational thinking

Question 1

What is abstraction

Answer 1

breaking down problems to their essential features

Question 2

What is representational abstraction

Answer 2

removing unnecessary details so that only the information needed to solve the problem is left

Question 3

what is abstraction by generalisation/categorisation?

Answer 3

reducing problems by putting similar aspects of a problem into hierarchal categories.

Question 4

What is functional abstraction

Answer 4

breaking problems down into functions

Question 5

What is top down design?

Answer 5

breaking a problem down from the most important to least important systems in a tree like diagram

Question 6

what is data abstraction?

Answer 6

hiding how data is represented to allow it to be represented as a different object ( like building a stack from an array)

Question 7

What is problem abstraction

Answer 7

identify an underlying problem in the aim that its already been solved.

Question 8

what is information hiding?

Answer 8

the process of providing a definition or interface of an object while hiding how it truly works

Question 9

What is decomposition?

Answer 9

breaking tasks into smaller tasks

Question 10

what is composition

Answer 10

building a system from smaller units.

Question 11

What is a Turing Machine?

Answer 11

a finite state machine that can read or write data to an unlimited tape

there is a start state and any state with no outgoing transition is called a halting state

Question 12

What is a universal machine?

Answer 12

a machine that can simulate a Turing machine by reading a description of the machine as well as an input of its own tape

Question 13

What is a regular language?

Answer 13

any language that can be described using reg-ex

Question 14

what is reg-ex?

Answer 14

a notation form that contains strings of characters that can be matched to the content of a set.

Question 15

What is a context free language?

Answer 15

an unambiguous way of describing the syntax of a language, where the syntax is complex.

Question 16

What is Backus-Naur form

Answer 16

a form of notation used to describe the syntax used by a programming language.

Question 17

What is a syntax diagram

Answer 17

a method of visualising rules written in BNF or other context free languages.

Question 18

what is space complexity?

Answer 18

how much space an algorithm requires

Question 19

What is time complexity

Answer 19

How much time an algorithm requires

Question 20

what is O(1)

Answer 20

constant time

Question 21

what is O(N)

Answer 21

when the time taken to run is directly proportional to the input size (linear search)

Question 22

what is O(n**2)

Answer 22

polynomial time, where the time is proportional to the square of the input size.

Question 23

what is O(2**N)

Answer 23

exponential time where the runtime doubles for each input

Question 24

what is O(logN)

Answer 24

logarithmic time

Question 25

how do u derive big O notation

Answer 25

• No data loops or recursion will be O(1)
• loops through an array once will be O(N)
• nested loops will be O(N^2) plus 1 to the power for each nested loop
• recursion is O(x^N)