CS 10 Elements of computational thinking

Computational thinking

The ability to think logically about a problem and apply techniques for solving it

Abstraction

removes unnecessary details to simplify complex things. It is a means of hiding detail/only using relevant detail, it is a representation of reality.

Representational abstraction

A simpler version directed at solving a particular problem. Like the London Tube map, or a flight simulator

Abstraction by generalisation

Grouping together similarities within a problem to identify what kind of problem. Allows problems to be categorised as being of a particular type. common in OOPS

Procedural abstraction

Allows programmers to utilise functions without knowing how they are implemented

Functional Abstraction

the implementation detail of the computational method is hidden (like print statement)

Data Abstraction

A form of abstraction where the details of how the data is actually stored are hidden

The need for abstraction

• Allows non-experts to use of a range of systems or models by hiding

• information that is too complex or irrelevant to the system’s purpose

• Enables for efficient software design

• Reduces the time spent on a project

• Prevents a program from getting unnecessarily large

How programming languages uses abstraction

• Low-level languages directly interact with computers but difficult to write

• High-level languages abstract machine code executed when a program is run by providing easy syntax similar to human language

• Makes coding accessible to non-specialists

How is the TCP/IP model an abstraction for how networks function

• Separated into four layers: application, transport, internet and link

• Each layer deals with a different part of the communication process

• Each layer does not need to know how other layers function

how are OOPs an abstraction for real world entities

Attributes are an abstraction for the characteristics of an object while methods are an abstraction for the actions a real-world object is able to perform.

what is problem reduction

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

Advantage of documenting inputs and outputs

no ambiguity in what must be supplied to the sub procedure and what is returned

what happens if we don’t specify I&O

creating an algorithm becomes much more difficult and can cause errors and problems later on when unexpected events occur

Preconditions

Conditions that must be true for an algorithm to complete successfully, without errors or crashing

Advantages of specifying preconditions

• The developer is aware of what checks are required and not required before calling the subroutine

• Allows the subroutine to be reusable and put into a library and called on at any time if there is clear documentation

• Makes programs easier to debug and maintain

3 examples of reusable components

• abstract data structures

• classes

• subroutines

Standards for reusable modules

• inputs, outputs, and preconditions are specified

• identifiable variable names

• local variables

Advantages of subroutines

• programs are shorter and easier to understand and reuse

• easier to debug program - you can test procedures separately rather than the whole program

• when creating large programs, coding can be divided amongst devs

• if changes made to subroutine, then changes will be applied to wherever it is used

• can be added to library so it can be used in other programs

• saves time

What is caching

caching is the temporary storage of frequently/recently used data and instructions within a cache, allows faster access for future use. It is how a computer ‘thinks ahead’

What does structured programming use

• modularisation for program structure and organisation

• recursion

what is a top down design (stepwise refinement)

• the program is divided into subprocedures, or modules

• any of the sub procedures may be broken down into smaller subtasks

• each subtask can be solved by a single subroutine

• a hierarchy chart is often used to show the overall program structure

what is decomposition

splitting a problem down into component parts/subprocedures/modules

Modularisation advantages

• modularity

• debugging

• resuability

• scalability

• collaboration

• reliability

• reduced complexity

• maintainability

• readability

Two types of logical arguments

• deductive

• inductive

Deductive logical arguments

the conclusion follows on from the premises; if the premises are true, the conclusion must be true

Inductive logical arguments

seeks to make a strong case to support the conclusion; if the premises are true, the conclusion is highly likely to be true

What is thinking concurrently/concurrent processing

• instructions are processed at the same time/overlapping times

• one process doesn’t have to finish before the other starts

Parallel processing is when

breaking down a task into smaller, independent subtasks that can be executed simultaneously on different processors or cores

how does concurrency differ from parallism

Multiple tasks make progress simultaneously, but not necessarily at the same moment. Single processor switches rapidly between different tasks, creating impression of simultaneous execution.

Multicore processing

shares same buses and stuff, with each having its own cache

examples of concurrent processing

• video editing

• image processing

• facial recognistion

• 3D stereo games and applications

• virus scans

benefits of concurrent processing

• increased program throughput - 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

draw backs of concurrent processing

• if a large number of users trying to run programs, and some of these involve a lot of computation, then these programs will take a lot longer to compute

• an overhead in coordinating and switching processes, which reduces program throughput

Benefits of parallel processing

• enable several tasks to be performed simultaneously by different processors, can speed up processing enormously

• graphics processors can quickly render a 3D object by working simultaneously on individual components of the graphic

drawback of parallel processing

there is an overhead in coordinating the processors and some tasks may run faster with a single processor than with multiple processors

Methods of problem solving

• enumeration

• simulation

• theoretical approach

• creative solution

• exhaustiev search

characteristics of problems able to be solved computationally

• clearly defined

• needs to be computable

• data requirements

• whether it can be approached using decomposition and abstraction

under what condition is a problem defined as being computable

if there is an algorithm that can solve every instance of it in a finite number of steps

exhaustive search

trying all possible solutions to a problem - brute force

ennumeration

process of listing items or elements one by one in a systemic way

Simulation

the process of designing a model o a real system in order to understand the behaviour of the system, and to evaluate various strategies for its operation

strategies for problem solving

• divide and conquer

• problem abstraction

• automation

what is automation

building and putting into action models to solve problems

Backtracking

a methodical way of trying out different sequences until you find one that leads to a solution, often uses recursion,

where is backtracking used in

• computer networking

• web page structure

• social media connections

what is an intractable problem

a problem that can’t be solved

data mining

process of collecting, storing, and analysing huge amounts of data to find connections and associations in order to make predictions

big data

the term used for large sets of data that can’t be easily handled in a traditional database

3 major features of big data

• volume: when the volume increases from mega to giga to tera/peta

• variety: data changes from structured (lists) to unstructured (photos)

• velocity: the periodicness of data, how often collected or real time (like stocks)

Pipelining

• Carrying out instructions concurrently

• The result from one process/procedure feeds into the next

• different tasks developed in parallel

where is pipelining used

• cpu instruction fetching

• social media platforms collecting data in real time

performance modelling

when the behaviour of something is tested or simulated before it is used in the real world, mathematical methods used to test various loads on different operating system. cheaper. safer, less time consuming method of testing applications

visualisation

data presented in a way that is easier for us to understand using graphs, trees, charts. makes it easier to identify trends

Heuristics

non-optimal, educated guesses, ‘rule of thumb’ approach to problems that don’t necessarily provide the optimal solution. used for finding solutions to intractable problems