4. Theory of Computation Flashcards
What is an Algorithm?
An Algorithm is a sequence of steps to solve a problem
What is Assignment?
Assignment is when a value is given to a Variable.
What do Sequence, Selection and Iteration refer to?
Sequence - code is executed line by line from the top of the program to the end.
Selection - 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 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 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 Functional Abstraction?
Functional Abstraction is the use of Functions which map a set of inputs to a set of outputs, this is independent of how that mapping is computed.
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 Problem Abstraction?
Problem Abstraction is the removal of details from a problem until it reduces to an already solved problem with known properties.
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 Automation?
Automation is when a model of a real world process is used to generate actions which in turn affect that real world process. For example Climate Models can be used to predict the effect of various policy choices, which could then be used to decide what policy to put into action.
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
Identify the Time Complexities of the following Algorithms:
Bubble Sort,
Linear Search,
Merge Sort,
Binary Search
Bubble Sort is O(n^2)
Linear Search is O(n)
Merge Sort is O(n log n)
Binary Search is O(log n)
What is the difference between Tractable and Intractable problems?
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.
