2.1 - Elements of Computational Thinking

Page 1

2.1.1 - Thinking Abstractly

Abstraction Applied to High-Level Languages:

First Generation of Language:

Machine Code.

Represented using binary.

Writing a program to solve the simplest of problems was a tedious and time consuming task.

Second Generation of Language:

Mnemonic codes were used to represent instructions.

Assembly language.

Can be very difficult to design complex programs.

Has to be rewritten for new hardware.

Third Generation of Language:

Used statements that removed all the tedious details of where everything is stored and all other implementation details.

High level languages, such as Python.

Programmers can focus on the problem rather than worrying about irrelevant technological details.

Representational Abstraction:

A representation arrived at by removing unnecessary details.

Examples:

A computer model of the environment, a car or simulator.

A game, and the important details required for it.

The map of a train line, such as the London Underground.

Abstraction by Generalisation:

Removing all irrelevant details, and replacing key parts with general forms of the corresponding objects:

For example, a map of an island with bridges coming off could be represented as a block with lines coming off.

The lines can all be the same size in width, and the same colour, as the details of the bridge do not matter.

Groups by common characteristics to arrive at a hierarchical relationship.

Very common in object oriented programming

Data Abstraction:

Details of how data is represented are hidden.

Abstract data types can be created, which are logical descriptions of how data is viewed, rather than how they are actually represented.

Page 2

2.1.2 - Thinking Ahead

Computational Problems:

At its most abstract, a computational problem can represented as:

Input -------> Computational Problem ------------> Output

An input is the information relevant to the problem, which could be used to solve it.

An output is the actual solution to a problem.

Preconditions:

A condition that must be fulfilled before an algorithm can work.

For example:

A precondition could be that we assume all values being inputted into a function are positive (as negative values may cause a crash).

Advantages:

Ensures that the user knows what checks must be carried out before calling a subroutine.

Without preconditions, the user knows that necessary checks will automatically be carried out.

Clear documentation of all inputs, outputs and preconditions makes each subroutine reusable.

Reusable Program Components:

Libraries of resuable components can be created.

These components have already been written, tested and debugged, thus saving development time and the cost of producing them.

Caching:

Automatically done by the operating system.

The temporary store of instructions or data that have been used and may be needed again, for quick retrieval.

Web Caching:

Stores HTML pages so that they do not need to be downloaded again, saving bandwidth.

Drawbacks:

Data is not updated when stored in cache, so if it is updated the value in cache will be outdated.

Page 3

2.1.3 - Thinking Procedurally

Procedural Abstraction:

Using a procedure to carry out a sequence of steps to complete a task.

The programmer does not need to know what a procedure does, or how it works; they only need to know what the output is and the parameters that need to be passed to it.

Problem Decomposition:

Breaking down a problem into sub-problems until each sub-problem can be self-contained in its own function or procedure.

Advantages:

Makes the task of writing the program much easier.

Much simpler to test and maintain.

When a change is made, each module is self-contained so any changes made will only impact the module and not the rest of the program.

Any errors that occur can be traced to a single instance of a module.

Page 4

2.1.4 - Thinking Logically

Programming Constructs:

Sequence - one statement following another.

Selection - IF and Case statements.

Iteration - While, For... statements.

Concepts of Logical Thinking:

You need to be able to:

Identify points where decisions are made in an algorithm.

Determine the conditions that affect the outcome of a decision.

Determine how decisions affect the flow of a program.

Page 5

2.1.5 - Thinking Concurrently

Parallel Computing:

Requires multiple processors each executing different instructions simultaneously.

Aims to speed up computations.

Impossible on a single processor.

Benefits:

Enables several tasks to be performed simultaneously.

Graphics processors can render objects by working simultaneously on individual components.

Browsers can display several web pages in separate windows or tabs.

Drawbacks:

There is an overhead in coordinating the processors, where some tasks may run faster with a single processor instead.

Concurrent Processing:

Related to, but distinct from parallel computing.

When several processes are running, with each being given a slice of processor time.

You need to be able to determine parts of a problem that can be tackled at the same time.

Gives the appearance that several tasks are being performed simultaneously, despite only one processor being used.

Benefits:

Increased program throughput - number of tasks completed in a given time is increased.

Time that would be wasted is used on other tasks.

Drawbacks:

A large number of users trying to run programs will take longer to complete.