Section Ten: Computational thinking

Question 1

Chapter 47 – Thinking abstractly
Computational thinking

Answer 1

Computational thinking refers to the ideas and thinking skills used to design solutions to problems, or create systems so that a computer or computational agent can help

Question 2

Chapter 47 – Thinking abstractly
Abstraction

Answer 2

The representation of essential features without including unnecessary details. It is used to reduce the complexity of systems for users, hiding how things actually work, applying algorithms to different contexts and producing suitable user interfaces

Question 3

Chapter 47 – Thinking abstractly
Data abstraction

Answer 3

A similar idea is that of data abstraction.
The details of how data are actually represented are hidden. For example, when you use integers or real numbers in a program, you are not interested in how these numbers are actually represented in the computer.

Question 4

Chapter 48 – Thinking ahead
Computational problems

Answer 4

Input is the information relevant to the problem, which could for example be passed as parameters to a subroutine.

Output is the solution to the problem, which could be passed back from a subroutine. A clear statement of exactly what the inputs and outputs of a problem are is a necessary first step in constructing a solution.

Question 5

Chapter 48 – Thinking ahead
Advantages of specifying preconditions

Answer 5

• Specifying preconditions as part of the documentation of a subroutine ensures that the user knows what checks, if any, must be carried out before calling the subroutine.
• If there are no preconditions, then the user can be confident that necessary checks will be carried out in the subroutine itself, thus saving unnecessary coding. The shorter the program, the easier it will be to debug and maintain.
• Clear documentation of inputs, outputs and preconditions helps to make the subroutine reusable. This means that it can be put into a library of subroutines and called from any program with access to that library.

Question 6

Chapter 48 – Thinking ahead
Nature and benefits of caching

Answer 6

Caching is another aspect of thinking ahead, this time done automatically by the operating system rather than the programmer. Caching is the temporary storage of program instructions or data that have been used once and may be needed again shortly. The last few instructions of a program may be stored in cache memory for quick retrieval.

Web caching, i.e. the storing of HTML pages and images recently looked at, is another example of caching. This gives fast access to pages that have been recently looked at (and may be returned to) and saves having to download pages again, using up bandwidth unnecessarily.

Question 7

Chapter 49 – Thinking procedurally
Procedural abstraction

Answer 7

Procedural abstraction means using a procedure to carry out a sequence of steps for achieving some task such as calculating a student’s grade from her marks in three exam papers, buying groceries online or drawing a house on a computer screen.

Question 8

Chapter 49 – Thinking procedurally
Problem decomposition

Answer 8

Most computational problems beyond the trivial need to be broken down into sub-problems before they can be solved. Think of any system which starts off by presenting the user with a menu of choices. Each choice will result in a different, self-contained module.

Question 9

Chapter 49 – Thinking procedurally
Top-down design

Answer 9

Top-down design is the technique of breaking down a problem into the major tasks to be performed; each of these tasks is then further broken down into separate subtasks, and so on until each subtask is sufficiently simple to be written as a self-contained module or subroutine. Remember that some programs contain tens of thousands, or even millions, of lines of code, and a strategy for design is absolutely essential. Even for small programs, top-down design is a very useful method of breaking down the problem into small, manageable tasks.

Question 10

Chapter 49 – Thinking procedurally
Advantages of problem decomposition

Answer 10

As well as making the task of writing the program easier, breaking a large problem down in this way makes it very much simpler to test and maintain. When a change has to be made, if each module is self- contained and well documented with inputs, outputs and preconditions specified, it should be relatively easy to find the modules which need to be changed, knowing that this will not affect the rest of the program.

Question 11

Chapter 49 – Thinking procedurally
Hierarchy charts

Answer 11

A hierarchy chart is a tool for representing the structure of a program, showing how the modules relate to each other to form the complete solution. The chart is depicted as an upside-down tree structure, with modules being broken down further into smaller modules until each module is only a few lines of code (never more than a page).

Question 12

Chapter 50 – Thinking logically, thinking concurrently
The structured approach

Answer 12

The structured programming approach aims to improve the clarity and maintainability of programs.
Using structured programming techniques, only three basic programming structures are used:
- sequence – one statement following another
- selection – if … then … else… endif and switch/case … endswitch statements
- iteration – while … endwhile, do… until and for … next loops

Languages such as Python and Pascal are block-structured languages which allow the use of just three control structures. They may allow you to break out of a loop, but this is not recommended in structured programming. Each block should have a single entry and exit point.

Question 13

Chapter 50 – Thinking logically, thinking concurrently
Tools for designing algorithms

Answer 13

Flow diagrams and pseudocode are two methods or tools which are commonly used for designing algorithms. Pseudocode corresponds more closely to the iteration structures in a programming language and is generally more useful for designing algorithms of any complexity.

Question 14

Chapter 50 – Thinking logically, thinking concurrently
Thinking concurrently

Answer 14

The difference between concurrent computing and parallel computing is debatable and is often taken to mean the same thing. For example, a house may have a burglar alarm system which continually monitors the front door, back door, windows, rooms upstairs and downstairs.

Generally, concurrent computing is defined as being related to but distinct from parallel computing. Parallel computing requires multiple processors each executing different instructions simultaneously, with the goal of speeding up computations. It is impossible on a single processor.

Concurrent processing, on the other hand, takes place when several processes are running, with each in turn being given a slice of processor time. This gives the appearance that several tasks are being performed simultaneously, even though only one processor is being used.

Question 15

Chapter 50 – Thinking logically, thinking concurrently
Benefits and trade-offs of concurrent processing

Answer 15

Concurrent processing has benefits in many situations.
- Increased program throughput – the number of tasks completed in a given time is increased
- Time that would be wasted by the processor waiting for the user to input data or look at output is used on another task
- The drawback is that If a large number of users are all trying to run programs, and some of these involve a lot of computation, these programs will take longer to complete

Question 16

Chapter 50 – Thinking logically, thinking concurrently
Benefits and trade-offs of parallel processing

Answer 16

• Parallel processors enable several tasks to be performed simultaneously by different processors. It can speed up processing enormously when repetitive calculations need to be performed on large amounts of data
• Graphics processors can quickly render a 3-D object by working simultaneously on individual components of the graphic
• A browser can display several web pages in separate windows and one processor may be carrying out a lengthy search or query while processing continues in other windows
• parallel processing has limitations; there is an overhead in coordinating the processors and some tasks may run faster with a single processor than with multiple processors.

Question 17

Chapter 51 – Problem recognition
Computable problems

Answer 17

A problem is defined as being computable if there is an algorithm that can solve every instance of it in a finite number of steps. Some problems may be theoretically computable, but if they take millions of years to solve, they are, in a practical sense, insoluble.

An example of such a problem is the cracking of a secure password. If you choose a password of 10 characters or more, comprising a mixture of random letters, numbers and special symbols, it will be impossible to crack. You can test the strength of your passwords on various websites.

Question 18

Chapter 51 – Problem recognition
Methods of problem solving

Answer 18

There are many ways of problem solving, including:
- enumeration (listing all cases)
- simulation
- theoretical approach
- creative solution

Question 19

Chapter 51 – Problem recognition
Enumeration

Answer 19

Enumeration is defined as the process of extracting user names, machine names, network resources, shares and services from a system

Question 20

Chapter 51 – Problem recognition
Simulation

Answer 20

Simulation is the process of designing a model of a real system in order to understand the behaviour of the system, and to evaluate various strategies for its operation.
Such problems include:
- financial risk analysis
- population predictions
- queueing problems
- climate change predictions
- engineering design problems
Simulating a system invariably makes use of abstraction to reduce the problem to its essentials, removing all unnecessary details. Queueing problems, for example, include problems of finding out how many checkouts are needed in a new supermarket or on a new toll road, or how many staff are needed in a software support department to man the helplines, or in a tax office to process tax returns.

Question 21

Chapter 51 – Problem recognition
Strategies for problem solving

Answer 21

Divide and conquer
Problem abstraction
Automation

Question 22

Chapter 51 – Problem recognition
Divide and conquer

Answer 22

This is a very powerful technique which essentially reduces the size of the problem with every iteration. Its best-known application is the binary search, which halves the size of the problem with each iteration. Other problems may be tackled in this way but do not necessarily reduce the problem so fast.

Question 23

Chapter 51 – Problem recognition
Problem abstraction

Answer 23

Problem abstraction involves removing details until the problem is represented in a way that it is possible to solve because it reduces to one that has already been solved.

Question 24

Chapter 51 – Problem recognition
Automation

Answer 24

Automation in computer science deals with building and putting into action models to solve problems. For example, you could model the financial implications of running an ice cream stand at a given venue for a week or a longer period. You have to decide on what has to be included in the model and what assumptions you are going to make. Then you have to create and implement the algorithms and execute and test the results.

Question 25

Chapter 52 Problem solving
Visualisation

Answer 25

The manner in which a problem is presented is often a very important factor in finding a solution. Computers work with binary numbers but humans often prefer a visual image.

Question 26

Chapter 52 Problem solving
Backtracking

Answer 26

In some problems, in order to find a solution you have to make a series of decisions, but there may be cases for which:
- you don’t have enough information to know which is the best choice
- each decision leads to a new set of choices
- one or more of the sequences may be a solution to the problem

Backtracking is a methodical way of trying out different sequences until you find one that leads to a
solution.

Question 27

Chapter 52 Problem solving
Data mining

Answer 27

Data mining is the process of digging through big data sets to discover hidden connections and predict future trends, typically involving the use of different kinds of software packages such as analytics tools. Big data is the term used for large sets of data that cannot be easily handled in a traditional database.

Question 28

Chapter 52 Problem solving
Intractable problems

Answer 28

Some problems are termed intractable because although an algorithm may exist for their solution, it would take an unreasonably long time to find the solution. An example of such a problem is known as the Travelling Salesman Problem (TSP), which poses the question “Given a list of towns and the distances between each pair of towns, what is the shortest possible route that the salesman can use to
visit each town exactly once and return to the starting point?”

Question 29

Chapter 52 Problem solving
Heuristic methods

Answer 29

Heuristics are mental shortcuts for solving problems in a quick way that delivers a result that is sufficient enough to be useful given time constraints. Investors and financial professionals use a heuristic approach to speed up analysis and investment decisions.

Question 30

Chapter 52 Problem solving
Performance modelling

Answer 30

Performance modelling is the process of simulating different user and system loads on a computer using a mathematical approximation, rather than doing actual performance testing which may be difficult and expensive. For example, it could be used to test the performance of a network under different conditions. The output from the performance model may then be used to help with planning a new system which is suited to the requirements of an organisation.