Paper 2 Flashcards
variable
named locations that store data in which the contents can be changed during program execution
local variable
declared inside a function. They can only be accessed and used in that function.
global variable
declared outside of all the functions, they can be used throughout the whole program including inside functions.
advantages of functions
easier to create and test
subprogram
self-contained units of code that perform some well-defined purpose.
function
a subprogram that ALWAYS returns a single value
procedure
a subprogram that returns one or many values.
parameter
the data that is supplied to a subprogram so that they can be reused
passing by reference
the address of the variable is passed to the subprogram.
if the variable is changed it stays changed.
passing by value
a copy of the variable is passed to the subprogram. The original variable is unchanged no matter what the subprogram does.
binary search precondition
the list needs to be sorted
Insertion sort
works by dividing a list into two groups: sorted and unsorted. Elements are inserted one by one into their correct position in the sorted section.
thinking abstactly
represents reality by recognising what is important and blocking out other details
thinking ahead
planning input and outputs e.g. caching
caching
a temporary store where data and instructions or data that are likely to be needed are stored.
Thinking procedurally
writing in modules to split a problem up into manageable tasks
Thinking Logically
inferring things from what you already know and understanding where decisions need to be made and their consequences
Thinking concurrently
thinking about how a job might be done better if some parts were performed at the same time.
features of an IDE
- Auto-complete
- colour coding/ syntax highlighting
- stepping
- breakpoints
- watch window
- error diagnostics
features of an IDE: Auto-complete
recognises identifiers
features of an IDE: colouring syntax
identifies different features making the code easier and quicker to check
features of an IDE: stepping
runs one line at a time to check the result, good for error checking
features of an IDE: breakpoints
stops the code at set points to check the value of variables, good for error checking
features of an IDE: watch window
tracks how variables change during the execution
features of an IDE: error diagnostics
locates and reports errors
IDE
Integrated Development Environment
What is an IDE
contains all the tools needed to write, develop and debug and program
IDE three main tools
- editor
- build facility (automates the process of constructing a program from its component parts)
- a debugger
Three programming constructs
sequence
selection
iteration
sequence
a series of statements that are executed one after the other
selection
a decision is made based on the state of a boolean expression
Iteration
where a section of code is repeated
Selection cause
IF statement/ CASE statement
branch in assembly
Iteration cuase
FOR loop / WHILE loop / REPEAT UNTIL loop
repeat until loop
Condition tested at the end of the loop
While loop
condition tested at the start of the loop
for loop
countrolled - repeats a set number of times
Recursion
A procedure calls itself.
alternative way of producing iteration.
causes stack overflow is no terminating condition is built in.
Source code
The code written by the user
Compiler
translates high level language.
produces an object-code file. This can be run directly from the operating system,
Interpreter
Translates high level language.
translates and executes the program line by line.
Modularity
separates the programs functionality into independent, interchangeable modules.
constant
named locations that store data in which the contents stay the same during program execution
object orientated programming
allows a program to solve problems by programming objects which interact with each other.
class
a template used to define an object. It specifies the methods and attributes an object should have.
object
an instance of a class
method
a subroutine associated with an object
new
a specific method called a constructor
constructor
a method that defines how an object is created
attribute
variables contained within and associated to an object
Encapsulation
ensuring private attributes can only be amended through public methods. Stops attributes being manipulated in unintended ways.
inheritance
the ability for a class to inherit the methods and attributes of a parent class. The child class can have its own methods and attributes and override the inherited methods and attributes.
polymorphism
the ability for objects of different classes to be treated in the same way.
polymorphism example
the same method may be applied to objects of different classes
overriding
The method in the child class can be different to the method in its parent class whilst still having the same name and parameters etc
examples of abstraction
- variables
- objects
- layers
- data structures
- entity-relation diagrams
well-defined problems
problems that are clear to understand and the solution has defined expectations.
ill-defined problems
messy problems which are not clear how to solve.
Stages of problem solving
- Understand the problem
- Devise a plan
- carry out the plan
- Review your work
Why do algorithms help
- helps understand the problem
- executed more quickly
- possible to resort to trial and error
problem recognition
The ability to recognize and acknowledge that an issue exists or that a situation needs attention in an existing process or program. The ability to define a problem and know exactly what it is.
Computable
a problem is computable is we can come up with an algorithm that will solve every instance of the problem in a finite number of steps.
intractable problem
a problem which cannot be completely solved.
problem decomposition
the process of taking a big problem and breaking it down into smaller problems until you fully explored the problems. Each of these smaller problems translate into one task which is more easily programmable as an individual module, function or procedure.
Top-down Problem solving
an approach to solve a problem that involves breaking down the main problem into sub-problems.
divide and conquer
a technique based around reducing the size of a problem with successive iterations. You look at a problem, apply some rules and discard any data that does not match then repeat the process with any information which is left. E.g. binary search.
divide and conquer advantages
- efficient
- short runtime
linked list
ordered data structure that uses pointers to sort and order the data items
linked list node two parts
- to store the actual data
2. to store the reference to the next node
benefits of linked lists
efficient at adding/removing data
drawbacks of linked lists
slow to search
adding data to linked lists
- input the data in the location indicated to by the free storage pointer
- update the free storage pointer to next free location
- update the pointer for the new node to point to the next free storage spot
removing data from linked lists
- find the data item you want to delete
- update the previous pointer to point to the next data item
- the node for the deleted item can be added to the free storage list
Trees
Hierarchical data structure with data related to the data above it in the tree
Binary tree
tree structure where each node can only have 0,1 or 2 child nodes
What doe each node contain in a tree?
- pointers to the next data items
- data
preorder
- start at root node
- traverse the left sub tree
- traverse the right subtree
inorder
- traverse the left sub-tree
- visit the root
- traverse the right sub tree
postorder
- traverse the left sub-tree
- traverse the right sub-tree
- return to the root node
preorder dot
left
postorder dot
right
inorder dot
under
what does preorder do
selects roots before leaves
what does inorder do
sorts the nodes
what does postorder do
slects leaves before roots
graph
a set of edges/arcs connecting vertices/nodes
digraph
has one or more edges that have an arrow indicating you can only go in one direction
thinking ahead example process
- what answers do we need?
- What do we need to know to get what we need?
Thinking procedurally process
- divide the problem into sub-problems
- do solutions already exist for any of the sub-problems
- how do the sub-problems interact with each other
Backtracking
the process of incrementally building up towards a solution, abandoning a partial success when the solution can’t be completed and then going back to a previously successful match.
When does a backtracking algorithm end
when there are no more possible solutions to the first problem
backtracking advanatges
more effective than brute force as a large number of solutions can be eliminated with a single test
concurrent programming
where one computation advances without waiting for all the other computations to complete.
data mining
where vast amounts of unconnected data is searched through, patterns are found and correlations are calculated.
There may be no predetermined matching criteria and a brute force approach may be used (alot of processing power)
Uses of data mining
- targeting ads/marketing campaigns
- Anticipating resource demands
- Detecting fraud and cybersecurity issues
- Finding connection between seemingly unconnected events
positives of data mining
- improves marketing
- improves the estimate of stock quantities
- ensure demands are met
- increase sales
negatives of data mining
- alot of processing power required
- privacy concerns
- misuse of information
- inaccurate data can cause a negative effect
Big data
very large amounts of data on a particular topic
Parallel Computing
algorithm tasks are executed concurrently on a cluster of machines or supercomputers, is fundamental to managing big data tasks
Heuristics
making use of experience to find an acceptable solution, for example, using ‘rules of thumb’, educated guesses, intuitive judgements or common sense.
how are heuristics derived
derived from previous experiences with similar problems.
Why are Heuristics used/ what is the solution like?
Heuristic methods are used to rapidly find a solution that is ‘good enough’, even though it might not be the optimal solution.
Heuristic method example
when analysing data only analyse and gather the data which is most likely to help
performance modelling
process of carrying out mathematical approximations of how well models perform
What does performance depend upon
complexity
performance modelling example
- how efficient a program is
- whether a computing can cope with the strain
pipelining
the process of taking a task and splitting it into smaller tasks and then overlapping the processing of each sub task to speed up the overall process.
pipelining example
the fetch decode execute cycle: For example, when one instruction is being fetched, another instruction is being decoded and the last is being executed.
Visualisation
The ability to picture a problem and its solution in a visual way. It is easier to understand structures in a visual way
Visualiation example,
flow diagrams
5 methods of problem solving
- enumeration
- simulation
- theoretical approach
- trial and error
- creative solution
enumeration (method of problem solving)
Designing an algorithm that performs an exhaustive search