5. Elements of computational thinking Flashcards
What is a Constant?
A Constant identifies a fixed value in memory.
What is a Variable?
A Variable identifies a value in memory which may change during the execution of the program.
What is Assignment?
Assignment is when a value is given to a Variable.
What is a Subroutine?
A Subroutine is a named block of code which can be called to perform a task.
What is a Function?
A Function is a Subroutine which returns a value when called.
Explain the use of a Call Stack in executing Subroutines.
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.
What is a Parameter?
Parameters are Local Variables which hold the input values to a Subroutine. The values input into a Parameter are called Arguments.
What is a Module?
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.
What is Representational Abstraction?
Representational Abstraction is the removal of detail from a problem until only the details required to solve the problem computationally remain.
What is Abstraction by Generalisation?
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).
What is Data Abstraction?
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).
What is Procedural Abstraction?
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.
What is Decomposition/Composition?
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.
What is Concurrent Processing?
Concurrent Processing is when different aspects of the same problem can be solved at the same time.
What do Sequence, Selection/Branching and Iteration refer to?
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.
What is Recursion?
Recursion is when a Procedure calls itself in order to repeat code. Recursion is an alternative to Iteration.
Describe a Divide and Conquer approach to Problem Solving.
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.
What is Backtracking?
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.
What is Data Mining?
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.
What is Pipelining?
Pipelining is when a task is broken into a series of overlapping tasks. Tasks may be processed at the same time to improve performance.
What is a Heuristic and when would you use one?
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.
What is Performance Modelling?
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.
What is Time Complexity, and what does n refer to in Big O notation?
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.
Put the following Time Complexities in Order:
O(n^2), O(log n), O(1), O(2^n), O(n)
O(1) < O(log n) < O(n) < O(n^2) < O(2^n)
Constant < Logarithmic < Linear < Polynomial < Exponential
