computational thinking

types of abstraction

• representational abstraction

• abstraction by generalisation

• data abstraction

• procedural abstraction

describe representational abstraction

analysing what key features in a problem are relevant to solving it and simplifying it

describe abstraction by generalisation

grouping similar features of a problem to identify what kind of problem it is (=categorisation of the problem and being able to use a common solution)

describe data abstraction

details about how data is being stored is hidden = use of abstract data structures e.g. stacks and queues

describe procedural abstraction

removing details about the code being used to provide the functionality =pushing/popping items off a stack

What is an abstract model

Simplified representation of a problem by removing unnecessary details and displaying the key features of the program

why is abstraction necessary

• hides information too complex/irrelevant (e.g. hides contents of subroutines)

• programmers only focus on key features of code

• efficient design/code= save time/space

2 applications of layers of abstraction

• networking (TCP/IP model) (= simpler to understand communication process)

• programming languages (HLL = easily remember syntax + easier for beginners, object-oriented programming abstracts real life objects)

purpose of thinking ahead

to account for difficulties/problems that may arise, and thinking about how components can be used in the best way possible= easy + intuitive use for users

-this is by thinking about inputs/outputs, preconditions, caching and reusable components

describe inputs and outputs of a system

inputs: data used to solve a problem (including the order/method they are inputted in) = user values or arguments

outputs: results of data after the problem has been solved relayed to the user

what are preconditions

requirements that must be met before a piece of code can run (e.g. correct arguments). These can be within documentation for the user to fulfil = shorter + simpler program with less time to debug

purpose of preconditions

Ensure that the necessary checks are carried out before the execution of a subroutine (by the user or as part of the subroutine= more reusable.

what is caching

instructions and values recently used are temporarily stored in cache = saves time + bandwidth fetching instructions/values again + convenient to user

what is prefetching

using an algorithm to predict which instructions/values are likely to be needed again/fetched and storing them in cache= saves waiting time

disadvantages of prefetching/caching

• algorithm may be inaccurate (due to making informed guesses)

• cache size limits effectiveness

• difficult to implement

• old/stale copies of data may be used

use of reusable program components

already tested+ compiled= reliable, saves time, money and resources (but may have compatibility issues)

standards of reusable components

• well-documented inputs, outputs and preconditions

• only using local variables conforming to standard convention

• documentation is in standard format

• necessary inclusions of code explaining the program

• modules no larger than one page

purpose of thinking procedurally

It helps break a problem into smaller parts/subproblems (problem decomposition) and the components of a solution (e.g. easier to think about the order of subroutines created+ how they interact)

= easier to understand/ design

-shown on structure diagram

method of program decomposition/ stepwise refinement

top down design (large problems are broken down into levels in a hierarchical structure to provide detail to problem components, with first level at the top)

-the subproblems will therefore be able to be coded as a subroutine + tested separately

advantages of problem decomposition

• splits a general problem into more detailed subproblems

• more feasible to manage

• can be split between people to code

• easier to decide if a task can use library functions/subroutines

describe structured programming

programming utilising modularization (breaking a problem into subroutines), structured code (sequence, selection, iteration), and recursion

=improved clarity/ quality

standard rules for reusable modules

• document inputs, outputs and preconditions

• variable identifiers conform to a standard convention

• all variables are local

• standard format documentation

• does not exceed one page

• necessary explanations of sections of code

advantages of subroutines

-easier to follow

-easier to find which module needs to be changed

-New features can be added by adding new modules

- easier to program and manage

-Each subroutine (i.e. module) can be individually tested

-can be re-used several times in a program

-can be reused from a library

-Several programmers can simultaneously work on different

-saves time

purpose of thinking logically

Thinking logically involves thinking about the decisions that need to be taken by the user and their outcomes in the program (represented by boolean expressions, and shown in if statements or while and do loops)

-decide how decisions are made (if statements, while/ do loops, etc. )

how to simplify decision process

• limit possible solutions by checking feasibility/ reasonability/ effectiveness/ convenience

• evaluation of options based on the above

• decision flow chart

purpose of thinking concurrently

Completes multiple tasks at the same time = spot patterns between different areas of the problem where concurrent processing can be applied (processor dividing processor time to multiple tasks at once)

advantages of concurrent processing

• less time taken to complete each task

• reduces wasted time waiting for input or user interaction (as multiple tasks can be completed in the meantime)

• increased program throughput

disadvantages of concurrent processing

• ineffective/ take longer when many users/tasks are involved

• some tasks may not be able to be processes concurrently

• overhead coordinator of concurrency is required= less program throughput (amount of information processed at once)

how to tell if a problem is computational

• if they can be solved by an algorithm in a finite, realistic amount of time

• solving it involves inputs, outputs and calculations

• reasonable processing speed, memory and power available

describe problem recognition

• Analysing strengths and weaknesses with the current way this problem is being solved

• Considering types of data involved including inputs, outputs, stored data and amount of data

describe divide and conquer algorithm

halving the size of a problem every iteration, and each subproblem is recursively solved every ‘conquer’ iteration and recombined during the ‘merge’ stage

• decrease and conquer involves reducing the problem size every iteration

problem solving strategies

• divide and conquer (e.g. binary search)

• abstraction (e.g. graph unfolding)

• backtracking

• data mining

• heuristics

• performance modelling

• pipelining

• visualisation

describe backtracking

A recursive algorithm that visits all paths and builds a solution based on the correct paths, backtracking (to a previous decision) when invalid

• e.g. depth-first graph traversals

describe data mining

process of collecting and finding patters/outlier in big data (large sets of data) = future predictions based on previous trends, connections between events, detecting fraud/cybersecurity issues

describe big data

• characterised by volume (amount), velocity (speed of collection) and variety (pictures, videos, searches)

• managed by parallel computing, which uses concurrent processing

describe heuristics

a non-optimal, rule-of-thumb estimation of a solution when the standard solution is too time-consuming/resource-intensive (e.g. untraceable problems)

• e.g. virus checking, DNA analysis, internet routing, building circuit boards, AI

describe performance modelling

using mathematical methods to test a variety of loads on different operating system (e.g. safety-critical systems)

• cheaper, less time-consuming, safer

• assess capabilities of a system

describe pipelining

different tasks are completed in parallel, with one task’s output being used for another task’s input (resembles production line)

• if there are decisions within the program, the pipeline needs to be reset/flushed= ineffective

describe visualisation

method of presenting data in a more understandable way (esp. statistical data)

• identify non-obvious trends

• presented as graphs, trees, tables, charts, etc.

list programming techniques

• sequence, selection, iteration

• recursion

• modularization, functions and procedures

• local/global variables

• use of IDE

• use of object-oriented programming

describe the process of recursion

• when a function calls upon itself, a new stack frame

• variables, parameters and return addresses are stored in the stack

• once a stopping condition is reached, the subroutine unwinds and data is popped off the stack frame

disadvantages of recursion

• inefficient use of memory

• may cause stack overflow (runs out of memory)

• difficult to trace

• tail recursion is a more efficient method of recursion

2 ways variables can be passed as parameters

• by reference

• by value

describe passing variables by value

a copy of the value is passed as a parameter, which acts as a local variable not affecting the global variable

describe passing variables by reference

the address of the parameter is passed into the subroutine, so changing the value changes the value at that memory address

what is IDE

Integrated development environment is a program used to write develop, debug code (e.g. PyCharm, IDLE, Microsoft Visual Studio)

describe features of an IDE

• stepping (monitor each line of code’s effect)

• variable watch (seeing how variable contents change within the program)

• breakpoint (setting a point where a program stops, based on a condition or a set point)

• source code editor (helps code writing by providing indentation, word autocompletion and syntax highlighting)

• debugging tools (provide run-time detection of errors)

• translator

purpose of testing different types of inputs

to make sure all bugs are removed before deployment (erroneous, valid, invalid, null, extreme)

abstract data types vs data structures

• ADT present logical descriptions of how data is organised & task performance (e.g. graphs)

• data structures are the concrete locations of data (e.g. arrays, stacks, queues)