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
How does an Insertion sort work?
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
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
enumeration example
find the solution to an anagram by testing every permutation of letters
simulation (method of problem solving)
The process of designing a model of a real system in order to understand the behavior of the system, and to evaluate various strategies for its operation
simulation examples
- Financial risk analysis
- Amusement park rides
- Population predications
- Managing inventory systems
- Queueing problems
Theoretical approach (method of problem solving)
the problem be broken down into pure theory and be represented by mathematics
Trial and error (method of problem solving)
If you don’t know how to solve a problem using trial and error may help the process/ completely solve the problem depending on its complexity.
creative solution (method of problem solving)
Finding a solution to a problem which doesn’t follow the expected algorithms and rules but still provides an alternative solution
Stack
Last in First Out data structure
Queue
First in First Out data structure
How do stacks work
- data is push to the top of the structure
- data is popped from the top of the structure
stack pointers
a single pointer points to the top of the tack and increments/decrements as data is added/removed
algorithm for PUSHING onto a stack
IF stack pointer = max THEN
report stack full
ELSE
set stack pointer = stack pointer + 1
set stack[stack pointer] = data
END IFalgorithm for POPPING off a stack
IF stack pointer = min THEN
report stack empty
ELSE
set data = stack[stack pointer]
set stack[stack pointer] = null
set stack pointer = stack pointer -1
END IFHow do Queues work
- data is pushed to the end of the structure
- data is popped from the start of the structure
Queue pointers
two pointers one pointing to the start the other pointing to the end. both increment as data is added/removed.
circular queues
the newest data to be added in stored in the location which is vacated by popped data at the start of the queue
algorithm for PUSHING onto a queue
not circular
IF start pointer =1 and end pointer = max THEN
report queue full
ELSE
set queue (end pointer + 1) = data
set end pointer = end pointer + 1
END IFalgorithm for PUSHING onto a queue
circular
IF start pointer =1 and end pointer = max THEN
report queue full
ELSE IF start pointer = end pointer +1 THEN
report queue full
ELSE
set queue (end pointer + 1) = data
set end pointer = end pointer + 1
END IFalgorithm for POPPING off a queue
IF start pointer = 0 THEN
report queue empty
ELSE
set data = queue [start pointer]
set start pointer = start pointer - 1computational thinking
Thinking about how a problem can be solved through formulating the problem and constructing the algorithm to solve it.
Abstraction within programming / why is it abstraction
programmers use high level language commands.
The complexity of the machine code behind it has been removed
advantages of thinking ahead/ preconditions
- the user knows what they have to do
- makes clear documentation easier to maintain
- user can be confident that necessary checks have been carried out
benefits of caching
instructions and data can be fetched alot quicker
drawbacks of caching
- algorithms choosing which data to be cached my chose wrong data
- if algorithms are inefficient it can make the performance worse
advantages of thinking concurrently
- increased program throughput
- time is never wasted on user input
disadvantages of thinking concurrently
- if too many programs are running it takes a long time to process
Advantages of recursion
- suited to some problems (some functions are naturally recursive)
- reduces the size of the problem (divide and conquer)
Disadvantages of recursion
- can run out of stack space due to too many function calls which causes stack overflow
- more difficult to trace
- requires more memory than iteration
- slower than iteration
Breakpoints
a set point which stops the program at that line
step through
executes each line of code when you click
purpose of testing
uncovered undetected errors
procedural programming examples
Python, Pascal, Basic
Object orientated examples
Java, Delphi, C+
Instantiation
The creation of a new object
Complexity
how well the performance of an algorithm scales as the size of data sets increase.
time complexity
the number of steps/line of code executed in an algorithm.
space complexity
the memory requirement for an algorithm
efficiency
time complexity and space complexity
BigO
a complexity notation. remove all coefficiants and just write the value of n with the largest exponent e.g. O(n)
O(1)
constant complexity
constant complexity
An algorithm that always executes in the same time regardless of the size of the data set. Best Algorithms.
O(log n)
Logarithmic Complexity
Logarithmic Complexity
An algorithm that halves the data set in each pass. Efficient with large data sets. Good algorithms.
O(n)
Linear Complexity
Linear Complexity
An algorithm whose performance is proportional to the size of the data set and declines as the data set grows. Fair algorithms.
O(n^a)
Polynomial complexity (quadratic, cubic etc)
Polynomial complexity (quadratic, cubic etc)
An algorithm whose performance is proportional to the square of the size of the data set. Significantly reduces efficiency with increasingly large data sets. Poor algorithms.
O(2^n)
Exponential Complexity
Exponential Complexity
An algorithm that doubles with each addition to the data set in each pass. Inefficient. Extremely poor algorithms that should be avoided.
O(n log N)
Algorithms that divide a data set but can be solved using concurrency on independent divided lists.
complexity order
O(1) -> O(logn) -> O(n) -> O(nlogN) -> O(n^2) -> O(2^n)
Linear search best
O(1)
linear search average
O(n)
linear search worst
O(n)
binary search best
O(1)
binary search average
O(logn)
binary search worst
O(logn)
Binary search tree best
O(1)
Binary search tree average
O(logn)
Binary search tree worst
O(n)
Hashing best
O(1)
Hashing average
O(1)
Hashing worst
O(n)
Breadth/Depth first best
O(1)
Breadth/Depth first average
O(V+E)
V = no. vertices
E = no edges
Breadth/Depth first worst
O(V^2)
Bubble sort best
O(n)
Bubble sort average
O(n^2)
Bubble sort worst
O(n^2)
Bubble sort space complexity
O(1)
Insertion sort Best
O(n)
Insertion sort Average
O(n^2)
Insertion sort Worst
O(n^2)
Insertion sort Space complexity
O(1)
Merge sort best
O(nlogn)
Merge sort average
O(nlogn)
Merge sort worst
O(nlogn)
Merge sort Space complexity
O(n)
Quick Sort best
O(nlogn)
Quick Sort average
O(nlogn)
Quick Sort Worst
O(n^2)
Quick sort space complexity
O(logn)
how to get the bigO expression
- remove all terms except the one with the largest exponent
- remove all constant factors
linear search
starts at the beginning of a list and checks each item in turn until the desired item is found
Binary search
divides a list in two each time until the item being searched for is found
Four sorting algorithms
Bubble, Insertion, Quick, Merge
Insertion sort words
Make the first item in the list the sorted list. The remaining items are the unsorted list.
While there are items in the unsorted list take the first item of the unsorted list.
While there is an item to the left of it which is smaller than itself swap with that item. End while.
The sorted list is now one item bigger.
End while
Merge sort
splits a list of size n into n lists of size 1. Each pair of lists are merged together in order until there is only one list of size n.
Why does merge split down into unit lists
because a list of length one is sorted
Merge algorithm
- If the sub-list is 1 in length, then that sub-list has been fully sorted
- If the list is more than 1 in length, then divide the unsorted list into roughly two parts. (An odd numbered length list can’t be divided equally in two)
- Keep dividing the sub-lists until each one is only 1 item in length.
- Now merge the sub-lists back into a list twice their size, at the same time sorting each items into order
- Keep merging the sub-lists until the full list is complete once again.
Quick Sort Algorithm
- If the list to be sorted is length 1, then finish - job complete
- Pick an item within the list to act as a ‘pivot’. The left-most item is a popular choice.
- Split the list into two parts - one list with items equal to or larger than the pivot item and the other list contains items smaller than the pivot
- Repeat this process on the two halves
Quick sort
The basic idea is to keep splitting a list into two smaller lists, sort those lists using the same quick-sort rules, then split the sub-lists and sort again, until there are only lists of 1 item or less left.
Where can the pivot be applied
The pivot can be applied to any item in the unsorted list.
advantages bubble
- simple
disadvantages bubble
- long time to run
advantages insertion
- Simple to code
- Good performance with small lists
- memory efficient
- good with sequential data
disadvantages insertion
- poor performance with larger lists
- not as quick as merge/quick sort
disadvantages quick
- difficult to implement
- if a bad pivot is picked the runtime is slow
- worst case efficiency is bad
advantages quick
- very efficient
- no additional storage required/ less stack memory
advantages merge
- Good for sorting slow access data
- Good for sorting sequential data
- if there are two equal values then positions are conserved, which is quicker
disadvantages merge
- It needs twice then length of memory space than the list
- If recursion is used, it used twice the stack memory as a quick-sort
- quick sort is faster
advantages Linear search
- Good Performance
- List does not need to be ordered
- Not affected by insertions and deletions
disadvantages linear search
- May be too slow over large lists
advantages binary search
- Works well with larger lists
- Quicker
disadvantages binary search
- Small lists simpler to use linear search
- Cannot deal with unordered lists
Depth first traversal
- uses a stack to store the visited nodes
- visits all the nodes attached to a node connected to a starting node before visiting a second node attached to a starting node
Depth first Algorithm
PUSH first node onto stack
mark as visited
Repeat
visit the next uninvited node adjacent to the node on top of the stack
mark as visited
PUSH this node onto the stack
if no node to visit POP node off the stack
UNTIL stack is emptyBreadth first Traversal
- uses a queue to store the visited nodes
- visit all the nodes attached directly to a starting node first
Breadth first algorithm
PUSH first node into the queue
mark as visited
REPEAT
visit unvisited nodes connected to the first node
PUSH nodes into the queue
UNTIL all nodes visited
REPEAT
POP next node from queue
REPEAT
visit unvisted nodes connected to current node
PUSH nodes onto queue
UNTIL all nodes visited
UNTIL all nodes visitedShortest path algorithms
Dijkstra’s and A*
Dijkstras table columns
visited, vertex, shortest distance from start node, previous vertex
What are all the shortest distances filled with at the beginning (Dijkstras)
infinity, except for the vertex your measuring from which is zero
Dijkstras
Finds the shortest distance between one node and any other node in a network
A*
A variation of Dijkstras that uses a heuristic to try and get the correct solution sooner
A* table
visited, vertex, shortest distance from start node, heuristic distance, sum, previous vertex
Advanatges of Dijkstras
- doesn’t need to know the target node before
- good for multiple target nodes
Disadvanatges of Dijkstras
- doesn’t work for negative edge weights
- slower than A*
Advantages of A*
- faster
- always find a solution if it exists
- can be morphed into other path finding algorithms by changing the heuristic
Disadvanatges of A*
- no good if you have many target nodes
- not good if you have no prior knowledge of the network
time complexity vs performance
even if the complexities are the same one algorithm may still perform better than another
Why are linked lists good for ordering list?
- dynamic data structure allows data to be added/removed
- data can be added/deleted from any point in the list
advantages of subprocedures
- can split between programmers (can specialize in their areas)
- speeds up completion time (multiple procedures are worked on concurrently)
- Easier to maintain/ test (can test each module invidiually)
- reuse modules saving time
What does depth first traversal use?
stack
What does breadth first traversal use
queue
Depth first traversal words
Depth-first goes to left child node when it can if there is no left child it goes to the right child when there are no child nodes the algorithm ‘visits’ it’ and backtracks to the parent node.
Breadth first traversal words
first visits the root. Breadth-first visits all nodes connected directly to start node then visits all nodes directly connected to each of those nodes (and then all nodes directly connected to those nodes and so on…)
how is backtracking used in depth first traversal
when there are no nodes to visit the algorithm goes back to the previous node to check for further nodes to visit
process of decomposition
splitting a problem down into its component parts
for loop pseudocode
for i=0 to 7
print(“Hello”)
next i
while loop pesudocode
while answer!=”computer”
answer=input(“What is the password?”)
endwhile
do until loop pseudocode
do
answer=input(“What is the password?”)
until answer==”computer”
MOD
gives the remainder of a division
DIV
integer division (rounds down)
if/else Pseudocode
if/else if entry==”a” then print(“You selected A”) elseif entry==”b” then print(“You selected B”) else print(“Unrecognised selection”) endif
switch/case pseudocode
switch/case switch entry: case “A”: print(“You selected A”) case “B”:1 print(“You selected B”) default: print(“Unrecognised selection”) endswitch
get the substring
stringname.subString(startingPosition, numberOfCharacters)
by default how are parameters passed?
by value
reading from a file
myFile = openRead(“sample.txt”)
x = myFile.readLine()
myFile.close()
writing to a file
myFile = openWrite(“sample.txt”)
myFile.writeLine(“Hello World”)
myFile.close()
procedure OO pseudocode
public procedure setAttempts(number)
attempts=number
endprocedure
Inheritance OO pseudocode
class Dog inherits Pet
attributes
methods
endclass
create an instance of a class OO
objectName = new className(parameters)
COmputable
if we can come up with an algorithm that will solve every instance of the problem in a finite number of steps it is computable.
Intractable problem
A problem that cannot be completely solves
Methods of problem solving:
- Enumeration
- Simulation
- Theoretical approach
- Trial and error
- creative solution
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.
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 codeable as an individual module, function or procedure.
Thinking ahead
planning inputs and outputs which may be used in a computer program.
Thinking procedurally
Dividing a problem into a series of sub problems are tackling each problem individually. Some will already have solution written which you can copy.
Thinking logically
inferring things from what you already know. Understanding where a decision needs to be made and knowing its consequences.
benefits of caching
- speeds up access times and therefore improves performance
- uses less physical resources
- increases throughput
drawbacks of caching
- it may not store the correct data, the data may no longer be relevant
- very complex trying to deal with data to be cached
- the physical memory is expensive
Why are reusable program components good?
- saves time and memory
- saves memory space
three types of error
- logical error
- systematic error
- run time error
logical error
An error that causes the program to perform something unintended
systematic error
Statement that break the rules of the programming language
run time error
Error that occurs due to an unexpected event/causes
the program to stop working (crashes)
advantages of writing in modules
- Work can divided between a team, saves time as work takes place in parallel
- each team must only know what values to go into their subroutine and their expected functionality
- breaks problem down, easier to understand/test/debug/read
- Modules can be given to teams with specific expertise
- each subroutine can be tested individually before its combined to the main program
- code can be reused
scope
The section of code where a variable can be accessed and used
local variables with the same name as global variables…
overwrite/ take precedence of global variables
modular design
program is split into self contained tasks which can be written and tested individually. Modules can be subdivided into smaller modules.
concatination
joining two strings together
Benefits of using recursion over iteration
- more natural to read
- Quicker to writes/ less lines of code
- Some functions are naturally recursive
- can reduce the size of the problem with each call
Drawbacks of using recursion over iteration
- can run out of stack space (due to too many function calls, causes it to crash)
- more difficult to trace/follow as each frame on the stack has different variables
- requires more memory
- Usually slower than iterative methods due to stack maintenance
Why are global variables sometimes used
When a variable needs to be accessed throughout the whole program and not just in one subroutine. e.g. a date variable
Why is the use of global variables usually avoided
- makes it difficult to integrate modules
- increases the complexity of a program
- easy to change the value by accident, leading to errors
non user defined function examples
int, input, print
function (inline)
a named section of code that performs a specific task and always returns a value.
what is more common: functions or procedures
function
Example rules for writing functions
- only allow functions to be of a certain length
- Suitably named variables
- functions must have a single entrypoint
- no/ few global varaiables
