5. Elements of computational thinking

Question 1

What is a Constant?

Answer 1

A Constant identifies a fixed value in memory.

Question 2

What is a Variable?

Answer 2

A Variable identifies a value in memory which may change during the execution of the program.

Question 3

What is Assignment?

Answer 3

Assignment is when a value is given to a Variable.

Question 4

What is a Subroutine?

Answer 4

A Subroutine is a named block of code which can be called to perform a task.

Question 5

What is a Function?

Answer 5

A Function is a Subroutine which returns a value when called.

Question 6

Explain the use of a Call Stack in executing Subroutines.

Answer 6

The Call Stack is used for memory allocation when a Subroutine is called. A Subroutine requires the following data: Parameters, Local Variables, and the return address. This data is allocated as a Stack Frame on the Call Stack. Every time a Subroutine is called it is allocating memory, and Subroutines calling other Subroutines build up the size of the Call Stack. If the Call Stack gets too big there will be a Stack Overflow which will crash the program, this is particularly an issue with Recursive Subroutines.

Question 7

What is a Parameter?

Answer 7

Parameters are Local Variables which hold the input values to a Subroutine. The values input into a Parameter are called Arguments.

Question 8

What is a Module?

Answer 8

A Module is a grouping of related code into an independent unit, such as a file or library. It is often good practice to break complex programs into a series of Modules. These may also aid code re-use.

Question 9

What is Representational Abstraction?

Answer 9

Representational Abstraction is the removal of detail from a problem until only the details required to solve the problem computationally remain.

Question 10

What is Abstraction by Generalisation?

Answer 10

Abstraction by Generalisation is the grouping of common characteristics until a problem can be related (“is a kind of”) to a structure with known behaviour (such as a graph).

Question 11

What is Data Abstraction?

Answer 11

Data Abstraction is the use of Abstract Data Types to structure data in the solution of a problem. An Abstract Data Type defines how its contents can be manipulated, but now how that behaviour is implemented. For example, a Stack Data Structure allows elements to be added (pushed) on to its top, or removed (popped) from its top, but could be implemented in several different ways (e.g. using an Array or a Linked List).

Question 12

What is Procedural Abstraction?

Answer 12

Procedural Abstraction is the use of Procedures/Subroutines which solve a group of similar problems. Specific problems can be solved by specifying different inputs to the Procedure.

Question 13

What is Decomposition/Composition?

Answer 13

Decomposition is the breaking a complex task into multiple sub-tasks which are simpler to solve. Composition is combining the solutions to simple tasks to solve a larger more complex task.

Question 14

What is Concurrent Processing?

Answer 14

Concurrent Processing is when different aspects of the same problem can be solved at the same time.

Question 15

What do Sequence, Selection/Branching and Iteration refer to?

Answer 15

Sequence - code is executed line by line from the top of the program to the end.
Selection/Branching - a choice is made between different possibilities, for example with an IF-statement.
Iteration - code is repeated using a loop structure, for example a FOR or WHILE loop.

Question 16

What is Recursion?

Answer 16

Recursion is when a Procedure calls itself in order to repeat code. Recursion is an alternative to Iteration.

Question 17

Describe a Divide and Conquer approach to Problem Solving.

Answer 17

Divide and Conquer breaks a problem into smaller sub-problems which may be simpler to solve individually. An example of Divide and Conquer would be the Binary Search or Merge Sort Algorithms.

Question 18

What is Backtracking?

Answer 18

Backtracking is used in algorithms which search for a solution to a problem, and then backtrack tracing their steps to produce that solution. An example of Backtracking is Dijkstra’s algorithm when used to find both the distance and shortest path to a goal.

Question 19

What is Data Mining?

Answer 19

Data Mining is a technique applied to Big Data, where large amounts of varying data is collected in a database. Data Mining is a family of techniques used to find unexpected relationships between varying data, which can then be exploited to solve problems.

Question 20

What is Pipelining?

Answer 20

Pipelining is when a task is broken into a series of overlapping tasks. Tasks may be processed at the same time to improve performance.

Question 21

What is a Heuristic and when would you use one?

Answer 21

A Heuristic is an assumption which simplifies a problem such that it is quicker to solve. A Heuristic may make it quicker to get a solution, but does not guarantee that you get the correct solution.

A Heuristic would be used to simplify an Intractable problem so that it behaves like a Tractable one, and allows bigger problems to be solved.

Question 22

What is Performance Modelling?

Answer 22

Performance Modelling is the testing of a system under a simulated load. For example simulating the effect of Network traffic on a Client-Server Application.

Question 23

What is Time Complexity, and what does n refer to in Big O notation?

Answer 23

Time Complexity is a way of describing how efficient an Algorithm is (or how difficult a problem is). It relates the time taken to solve a problem to the size of that problem. In Big O notation, n refers to the size of the problem. This may mean a different thing in different circumstances - it could be the size of a number, the length of an Array, or the number of nodes in a Graph, amongst many other possibilities.

Question 24

Put the following Time Complexities in Order:
O(n^2), O(log n), O(1), O(2^n), O(n)

Answer 24

O(1) < O(log n) < O(n) < O(n^2) < O(2^n)
Constant < Logarithmic < Linear < Polynomial < Exponential

Question 25

Identify the Time Complexities of the following Algorithms:
Bubble Sort,
Linear Search,
Merge Sort,
Binary Search

Answer 25

Bubble Sort is O(n^2)
Linear Search is O(n)
Merge Sort is O(n log n)
Binary Search is O(log n)

Question 26

What is the difference between Tractable and Intractable problems?

Answer 26

Tractable problems can be solved in Polynomial Time, whereas Intractable problems cannot. Tractable problems are generally well-behaved for modern computers, whereas Intractable problems grow too quickly to solve large problems.

Question 27

What is Object Oriented Programming?

Answer 27

Object Oriented Programming is where programs consist of Objects/Instances of Classes which interact with each other to implement behaviour.

Question 28

What is a Class?

Answer 28

A Class is a template for Objects/Instances. A Class may have Attributes (Variables attached to the Object) which represent its state and Methods (Subroutines/Functions attached to the Object) which represent its behaviour. Each Object maintains its own independent state which can change during the program by calling its Methods.

Question 29

What is Encapsulation?

Answer 29

Encapsulation is where an Object contains both its state (Attributes) and behaviours (Methods) together to represent some entity in the program. Each Object is independent of all other Objects, even if they are Instances of the same Class.

Question 30

What is Information Hiding?

Answer 30

Information Hiding is the use of Access Privileges to identify which Members (Attributes and Methods) of an Object can be interacted with by other Objects in the program. Public means that a Member can be accessed by any other Object. Private means it can only be accessed by other Instances of the same Class.

Question 31

What is Inheritance?

Answer 31

Inheritance is an “is-a” relationship between Classes (and Objects of those Classes). If a Dog Class inherits from a Mammal Class, then a Dog “is-a” Mammal, and has all the Members of the Mammal Class in addition to its own Members. Inheritance is a Parent Child relationship between Classes.

Question 32

What is Polymorphism?

Answer 32

An Object of a Class has the identity of that Class and any other Classes above it in the same inheritance hierarchy. This is called Polymorphism. For example, if a Dog Class inherits from a Mammal Class which also inherits from an Animal Class - then a Dog Object “is-a” Dog and a Mammal and an Animal. Anything that can be done to an Animal Object can also be done to a Dog Object, and likewise with a Mammal Object.