Elements of Computational Thinking

Made from P.M.T. and Ada comp. sci. notes

What is the shape used for decisions in a flowchart?

A (decision) diamond

In a flow chart how many options can you pick from a decision?

2 different options - yes or no/ true or false

How does the result of a decision affect the flow of a program?

The program will follow a different route depending on the result of a decision

What is abstraction?

• The process of separating ideas from reality.

• It is a representation of reality in which unnecessary detail is removed so that only the key features remain.

What kind of problems make use of multiple levels of abstraction?

Large, complex problems

How does abstraction allow non-experts to make use of a system?

Hides complex and irrelevant information in abstract models.

What are the advantages of abstraction?

• Simplifies the problem

• Less computation / data.

• Easier to see how the solution to one problem can also be the solution to another.

What are the advantages of using abstraction in software development?

• Simplifies the problem, making it easier for programmers to focus on core elements.

• This can reduces the time spent on a project and prevent a program from getting unnecessarily large

What is a disadvantage of abstraction?

Models will not be as accurate as reality

What are two examples of layers of abstraction in computer science?

• Networking (TCP/IP layer)

• Programming languages

What are two advantages of using abstraction in programming languages?

• Easier to remember syntax in high-level languages as it is closer to natural language

• Coding becomes accessible to beginners

How does object-oriented programming use abstraction?

• Objects are an abstraction for real-world entities.

• Attributes are an abstraction for the characteristics of an object.

• Methods are an abstraction for the actions a real-world object is able to perform.

What is the difference between abstraction and reality?

Abstraction is a simplified representation of reality, in which certain unnecessary details are removed

What is problem reduction?

The process of generalising or reducing a problem to one that has already been solved.

What is automation?

The process of taking the model and implementing a solution. This is achieved by:

• Implementing the data structures to store the data

• Implementing the algorithms to process the data

What is the first stage of thinking procedurally?

Taking the problem defined by the user and breaking it down into its constituent parts

What is the second stage of thinking procedurally in software development?

Identifying components of a solution

What are the advantages of thinking procedurally?

• Problems are easier to solve.

• Debugging is easier.

What is a disadvantage of thinking procedurally?

May not be entirely possible with an event driven rather than procedural approach to programming.

What is decomposition?

The process of breaking a problem down into smaller subproblems that can be solved individually and more easily

What is another name given to top-down design?

Stepwise refinement

What is the purpose of top-down design?

Continually break problems down into subproblems until each subproblem can be represented as a single task and ideally a self-contained subroutine.

What are the benefits of using top-down design?

• Problems can be solved and modules developed by different people.

• Tasks can be tested separately. Modules are self-contained

What types of problems is top-down used for?

Large, complex problems

How are the lowest level subproblems in top-down design implemented in code?

As self-contained modules or subroutines

What do software developers need to consider when recombining components of a solution?

The order in which subroutines are executed, and how they interact with each other, based on their role in solving the problem.

What should a software developer do before designing a new subroutine to solve a particular problem?

See whether it is possible to use an existing subroutine or module to solve the problem.

What are the advantages of utilising reusable components?

• They have often already been tested so are likely more reliable than newly-coded components

• As such less time is spent debugging and testing, which saves time, money and resources.

What is thinking ahead?

• The process of identifying the preconditions of a system: inputs, outputs, and reusable components.

• This means identifying what data is required before it is needed (caching) and identifying reusable program components.

What are the advantages of thinking ahead?

Caching can speed up a process

What are the disadvantages of thinking ahead?

• Caching can be complicated to implement.

• Caching requires the correct data to be fetched for the next instruction.

What is an input?

Any data that is required to solve a problem, usually entered into the system by the user

What is an output?

The results that are passed back once the inputs have been processed and the problem solved

What four considerations do programmers need to make about inputs and outputs when thinking ahead?

• Method of input/output (device used)

• Data structures used

• Data types used

• Order of data

What are preconditions?

Requirements which must be met before a program can be executed.

Where can preconditions be defined?

Within the code or within documentation.

What are four advantages of including preconditions within the documentation accompanying a subroutine?

• Reduces the length of the program

• Reduces the complexity of the program

• Saves time needed to debug and maintain a longer program

• Makes subroutine more reusable

Define caching

The process of storing instructions or values in cache memory after they have been used, as they may be used again

What is an advantage of caching?

Saves time as you don’t need to wait for instructions to be retrieved from secondary storage again

How is caching used in storing web pages?

Web pages that a user frequently accesses are cached, so the next time one of these pages is accessed, content can be loaded without any delay

What are the advantages of caching web pages?

• Content can be loaded without delay as less time is spent waiting

• Images and text do not have to be downloaded again multiple times

• Frees bandwidth for other tasks on a network

What limits the effectiveness of caching?

• Accuracy of the algorithms used

• Effectiveness of algorithm in managing the cache

• Size of the cache

What is prefetching?

When algorithms predict which instructions are likely to soon be fetched and are loaded and stored in cache

What is the name given to the technique in which algorithms are used to predict which instructions are likely to soon be used?

Prefetching

What is an advantage of prefetching?

Less time is spent waiting for instructions to be fetched

What are two advantages of using reusable program components?

• More reliable than new components, as they have already been tested.

• Since developing from scratch is not required, this saves time, money and resources.

What are three examples of reusable program components?

• Abstract data structures eg. queues and stacks

• Classes

• Subroutines

What is thinking logically?

• Identifying individual steps and decision points of an algorithm.

• This can involve:

  • Identifying the points at which a selection or iteration is needed.

  • Determining the conditions of the decision.

  • Determining the next steps depending on the outcome of the decision.

What are the advantages of thinking logically?

• Makes writing an algorithm easier.

• The complexity of an algorithm can be determined.

• Algorithms can be simplified, or better solutions found more easily.

• Identifies branches for testing.

What is concurrent processing?

When two or more tasks are in progress at the same time (but not necessarily being executed) simultaneously.

What is thinking concurrently?

Identifying parts of the problem that can be executed at the same time.

What are the benefits of concurrent processing?

• More efficient use of processor time, as the time that would be wasted by the processor waiting on a user (input) or another process is reduced.

• As such more tasks can be completed during a given time

• More efficient processing of interrelated tasks

What are the drawbacks of concurrent processing?

• There is an overhead in coordinating and switching between processes, which reduces program throughput.

• May be difficult to program.

• Can result in deadlock - when multiple tasks stop and wait on each other indefinitely

• Not all tasks are suited to being broken up and performed concurrently.

What is parallel processing?

• When multiple tasks are executed simultaneously

• They must be physically executing at the same time, for example on different cores of a multi-core processor.

• Parallel processing is a specialised form of concurrency

How is parallel processing physically achieved?

• By using multi-core processors and/or multi-processor infrastructure

• This means a single core CPU can not perform parallel processing

What is the difference between concurrent and parallel processing?

• Concurrency is about dealing with lots of things at once. This means multiple tasks are in progress, but not necessarily executing, at the same time

• Parallelism is about doing lots of things at once. This means (physically) executing multiple tasks at the same time.

• As such a single core CPU could perform concurrent processing (by spliting up its processor time between different tasks), but not parallel processing (as it cannot physically execute multiple taks at the same time with a single core)