Extra paper 2 Flashcards
How are flags used in bubble sort
flag is set if a swap is made in bubble sort
flag reset at end of each pass
Linked listrs are
Dynamic
Important way abstraction can be used in a game
abstraction can use symbols to represent elements of problem
What does abstraction increase the chance of
Creating the program succesfully
Depth first
Goes left until it cant and it visits that node and backtracks
Concurrent processing and individual processes, decribe what they are
Threads and each of them has a life line
Concurrent processing what sometimes needs to happen
One needs to start before a second one has finished
Concurret
Simulated multiple processes being carried out same time
Concurrent
Same time/overlapping times
What do programmers need to do with concurrent processingg
Allow multiple threads
Why is insertion preffered over bubble
Insertion sort is usually quicker than bubble sort because it minimizes the number of swaps by shifting elements instead of swapping the m
Declaritive1
Declarative languages are programming languages where you specify what the program should accomplish rather than explicitly outlining how to do it.
Why cannot a binary search work on a linked list
Items do not have to be in specific order for linked list but this is a requirement for binary search
What is autocomplete used for
View identifiers and avoid spelling mistakes whilst also speeding up progress
Colour coding/syntax highgliyinh
Can identify featrues quickly to be used to chech if code is correct
What is an insertion sort particularly useful for
Inserting items into an already sorted list
What are paradigms, dif
Way of writing software
Why does modular save time
Work done in parralel
IO have a cartd on this but WHy is performance modelling used
To simulate the behaviour of a system before it is used
Programming complexity for A* and dij
Minimal but if you can show the effects of each one
More memory locations needed
For local
What does quick sort use
Divide and conquer
What is divide and conquer
Taking two or more identical, smaller sub-problems from a larger problem, solving the sub-problems individually and combining their solutions to solve the original larger problem
Applications of quick sort
Real time situations, medical monitor, aircraft controls and life support systems and defence systems
What is quick sort good for
Ideal for parralel processing environments and large data sets
Why may merge sort use more memory than an insertion sort
*
Merge sort might create a new array each time it splits and merges / often implemented recursively which places additional data on the stack
*
Insertion sort does not use any additional arrays/Insertion sort is an in-place algorithm.
What should you say on a big o question,
what the best/worst case is
What does poassing by reference cause with recursion
It to crash
What can an IDE do with subroutines
Tell you the parameters you need to pass into it
What do IDE’s allow with running the software
Without exiting the software/having to load seperate compiler
Advantages of IDE’s
User friendly for novices
Increase speed of writing
Fewer mistakes
Increase speed of testing / finding errors
Collaborative team working facilitated
Insertion sort is an
In place algo whereas merge is not
What data is used for data mining
Data from databases and large data serts/big data
Data mining can be used to inform
Decisions
Data mining laws
GFPR
Variable watch
Variable watches are used to monitor the value of specific variables during the execution of a program. This helps in understanding how and when the values of those variables change.
Variable watch
Traces are used to record the execution flow of a program over time. This can include function calls, executed statements, and various events that occur during runtim
Do you have a visited column in A*
No
Drawback of concurrent processing
Concurrency involves overhead in terms of context switching, managing multiple threads or processes, and synchronization mechanisms. This overhead can sometimes outweigh the performance gains from parallel execution.
Security of conccurrent processing
Concurrency can introduce security vulnerabilities. Improper handling of shared resources and synchronization can expose the system to issues such as data leaks and unauthorized access.
Worst case insertion
Reverse order
Parameters v arguments
Parameters: Variables in the function definition.
Arguments: Actual values passed to the function when it is called.
Pipelining
The result from one process leads into next
Reference
Keeps the changes after
Advantages of global variables
Variable doesn’t need passing as a parameter (byref)
* You don’t need to return a value
* Can be accessed from any function / anywhere in the program
2 other advantages of reusable components
Variable doesn’t need passing as a parameter (byref)
* You don’t need to return a value
* Can be accessed from any function / anywhere in the program
When is breadth more efficient
Breadth is more efficient when the data
searched for is closer to the root.
When is depth more efficient
Depth is more efficient when data to be
search for is further down
Time complex of breadth and depth
Depth is more efficient when data to be
search for is further down
Can breadfthor depth use recursion
Depth can be written recursively to aid
understanding.
Memory for depth
Linear
graoghs v trees
Depth can be written recursively to aid
understanding.
Performance modellign tro minimise
Simulate/model behaviour of the system (before it is) used under load
* Because it would be too expensive/unsafe/time critical to test the real system
Queue for array
Queue has head pointer and tail pointer
* When an item is enqueued the tail pointer increments
* When an item is dequeued the head pointer increments
2 extra things to do when removing a node
Add node E to the empty node list
Replace the content of node E with blank/null/equivalent,
Extra thing for adding node
Make node K point to null/equivalent
Trees
1 direcctional
Trees and grapghs are bost
Dynamic
What divisions does decomp use
Logical divisions
n log n
Linearithmic
What can by ref cause
Crashes
What do IDE’s facilitate
Collaboration
What do compilers allow with runnign
Allow code to be run without exiting software/having to load a seperate compiler
IDE’s are
User friendly for novices
Iteration one
Harder to undestand but easier to trace
Objects are
Independant entities
Simple oop v procedural queues
Objects can declare any instance of this queue but procedural will need each queue to be declared individually and oop would reduce amount of code needed therefore reduce tchance of errors
Why would abstraction reduce development time
Factors that detract from program are ignored
Concurrent example to show like how to answer it with an LOR
Having multiple processors handling different requests would increase response time
Information hiding makes programs
Simpler
Disadvantage of large cache
Takes long time to search
Stakeholders and problem recognition
Stakeholders say what they need from the solution.
* This information is used to produce a clear list of system requirements and a
definition of the problem.
* We may consider the strengths and weaknesses of a current system.
* We may consider the required inputs, outputs and the volume of stored data.
what do heuristics provide an estimate for
Intractable problems
Other heuristic things
Performance Modelling
* Mathematical method to test loads on systems.
backtracking
When a leaf node is reached…
* …the traversal backtracks to the leaf’s parent node
* …backtracks to last node with unvisited children
Extra thing for problem recognition
determine if the problem can be solved with
computational methods
recognition: identifying the need for the
scheduling system, what it will take as its inputs,
what will need to be output etc.
Null
Does not point to another node, end of list
Explain how an item is added to a linked list
Check space available in the free list
* Check to make sure freeListPointer is not Null
Add new data item to first free space in free list
* Insert new data item at index freeListPointer
(index 4)
Append e.g.
* Traverse to / locate the end of the list (index 3
‘orange’)
* Set the pointer of the last item in the linked list to
freeListPointer (pointer at index 3 ‘orange’
changes from Null to 4)…
* … update freeListPointer to the location that
new data item pointer is pointing to at present.
(freeListPointer changes from 4 to 5)
* … update pointer from new data item to Null (index 4
pointer changes from 5 to Null)
Prepend e.g.
* Update freeListPointer to point to the location
that the pointer from the first item in the free list is
pointing to (freeListPointer changes from 4 to
5)
* … Update pointer from new data item to
headPointer (index 4 pointer changes from 5 to 1)
* … Update headPointer to the index of new data
item (headPointer changes from 1 to 4)
How are reusable components easier to maintain and debug
Easier error detection as fix once and it corrects in each place // less likely to
have errors as code is not written multiple times
* Makes it easier to maintain the program
Base case
May be one or more
What is concurrent processing
Processes happen at the same time // processes overlap
* One process can start before another one finishes
* Each process is given a slice of processor time
* Different processes can be executed (in parallel) by different processors/cores
Merge can apply
Concurent processing
Another thing for concurrent
different processors can carry out different processes for concurrent
Grapghs must
Cycles
What may data mining include
- May include pattern matching
algorithms - May involve anomaly detection
algorithm
Advantage of global variables with simplicity
= easier programming,
simpler to follow, easier to debug
Concurrent
One process does not have to finish before the other one starts
Which is recursive
Merge
Each thread
Runs indidually and overlaps
Reference v value memory
ByValue creates new memory
space…
* ByReference means existing
memory space is used
Quick
N log n but n squared worse, want pivot to be middle most number
In recursion which takes more memory
global
In larger trees
Depth may never return a value
Memory for … is linear
Depth
Depth first time complex
O(V+E) For both
