Theory of Computation

Question 1

Computational Thinking (definition)

Answer 1

Stating a problem in a way that can be solved using algorithms, and then constructing an algorithm to solve the problem in the most effective way

Question 2

Other name for computing

Answer 2

Automation of abstractions

Question 3

Representational abstraction (definition)

Answer 3

Removing excess details to represent a problem by only its key features

Question 4

Data abstraction (definition + example)

Answer 4

Hiding details about how data is being stored
e.g. programmers can use data structures without knowing how they are implemented

Question 5

Abstraction by generalisation (definition)

Answer 5

Grouping similarities in a problem to categorise it by a type, to then use a common solution

Question 6

Layers of abstraction (explanation + example)

Answer 6

Highest levels are closest to the user e.g. interface
Lowest levels are closest to reality e.g. interacting with machine components

Question 7

Procedural abstraction (definition + example)

Answer 7

Abstracting the values used in a computation (set of operations) to create a procedure e.g. using a subroutine without understanding the internal process of it

Question 8

Functional abstraction (definition)

Answer 8

Abstracting the computation method (operations) so that only the inputs and outputs are considered, creating a function

Question 9

Problem reduction/abstraction (definition)

Answer 9

Removing details from a problem until it can be represented in a way that is possible to solve, because it has been reduced to one that has already been solved

Question 10

Why is procedural abstraction needed? (explanation + examples)

Answer 10

Allows non-experts to hide information that is too complex or irrelevant for the systems purpose

e.g. 1: High level languages abstract machine code, making them easier to learn

e.g. 2: TCP/IP separates application, transport, internet and link so that each layer acts independently from the others

Question 11

Advantage and disadvantage of abstraction

Answer 11

+ allows models and predictions to be made
- too much abstraction will make a model untrue of real life

Question 12

The simplest abstraction of a computer

Answer 12

program
\/
Input > process > output
\/
storage

Question 13

Algorithm (definition)

Answer 13

Set of step-by-step instructions to solve a problem

Question 14

Why is abstraction needed? (explanation + example)

Answer 14

Removing unnecessary details and highlighting the most important ones improves clarity and makes the representation more useful for a function

e.g. flowchart is an abstraction of code

Question 15

Graph data structure (explanation)

Answer 15

Abstraction to the point where only the necessary data elements and relationships between them are shown (the nodes and connections)

Question 16

Why is thinking ahead important?

Answer 16

Maximise code efficiency and minimise errors

Question 17

What techniques would be considered “thinking ahead”?

Answer 17

1. Identifying inputs and outputs
2. Determining preconditions
3. Deciding what can be a reusable component
4. Caching

Question 18

Precondition (definition + example)

Answer 18

Something that must always be true in a solution to a problem e.g. must be below budget

Question 19

Reusable component (definition + examples)

Answer 19

Taking self-contained pre-tested code from another program and applying it the the current program

e.g. 1: subroutines
e.g. 2: libraries

Question 20

Benefits of reusing components

Answer 20

1. shortens development time
2. lowers development costs
3. reduces the amount of redundant code

Question 21

Application Programming Interface (definition + examples)

Answer 21

Set of functions allowing an app to access the features/data of another program e.g. the OS

e.g. Apple/Google password save

Question 22

Caching (definition + explanation)

Answer 22

Temporary storage of recently/frequently used instructions/data by the OS into cache
Results in faster retrieval times as less data needs to be fetched from secondary storage

Question 23

Web caching (definition)

Answer 23

Storing of HTML pages which have been recently looked at to avoid using up bandwidth if they are loaded again

Question 24

Prefetching (definition + explanation)

Answer 24

Data is requested from main memory before it is required
This reduces fetching time as it is faster to fetch from registers than from main memory

Question 25

How is prefetching managed?

Answer 25

Prefetching is managed by algorithms which predict with high accuracy that instructions/data will be needed soon

Question 26

Potential disadvantage of caching

Answer 26

Wrong data is fetched frequently and has to be removed, making it difficult to keep up with the correct sequence of instructions/data

Question 27

Top-down design/stepwise refinement (definition)

Answer 27

Technique for breaking down a problem into major tasks, then further breaking these down into subtasks, until each subtask is simple enough to be a self-contained module

Question 28

Advantages of decomposition

Answer 28

• Makes programming easier
• Makes code easier to test and maintain
• Some components may be reusable
• Specialists within a team can be designated the tasks most relevant to their speciality

Question 29

Hierarchy chart (definition)

Answer 29

Visual tool for representing the structure of a program, showing how “levels” of modules relate to form the solution - each module is no more than a page of code

Question 30

Problem recognition (definition)

Answer 30

Identifying where and what a problem is

Question 31

Why is procedural thinking important?

Answer 31

Some segments are event-driven so the order in which a user behaves can be largely unpredictable

Code reuse/ libraries / validation and sanitation techniques can be applied

Consider which variables are local/global

Question 32

Key aspects of procedural thinking

Answer 32

• Order of steps to a solution
• Identifying components of a problem
• Identifying solution functions/procedures for each problem component

Question 33

How can abstract thinking be defined + summarized?

Answer 33

Removing unnecessary details and including only relevant details

Question 34

How can thinking ahead be defined + summarized?

Answer 34

Identifying inputs, outputs, preconditions and reusable components of a system

Question 35

How can thinking procedurally be defined + summarized?

Answer 35

Breaking a large complex problem down into simple subtasks

Question 36

How can thinking logically be defined + summarized?

Answer 36

Identifying where decisions (selection) will be made, including conditions and outcome

Question 37

Three fundamental parts of a program

Answer 37

Selection - making a choice
Sequence - following instructions in an order
Iteration - repeating until a condition has been met