mistakes 2 Flashcards
linear s
Compare the search item with the first value
* ….then compare the search item with the next value
* ….repeat the above process until either
* ….the end of the array has been reached or
* ….the search item is found and then stop
* ….then return the array position // return -1 / False if not found
by value vs by reference
By reference the function receives the memory location of the data
* By value the function receives a copy of the variable
- By reference will make changes to the original variable
- By value will make changes to the copy of the variable
- By reference will overwrite data in the original variable
- By value will not overwrite the data in the original variable
- By reference will keep the changes after the function ends
- By value will not keep the changes after the function ends
define local and global
Local variables:
* Scope within the module defined
within
* Cannot access externally unless
passed as parameter, or returned
from function
* When module is exited, memory of
variable is freed
Global variables:
* Scope within the entire program
* Can access from anywhere
* Retained in memory permanently
ByRef Points to location of variable
ByVal Sends the value
Local adv + dis
need to be passed as parameters
byreference
Can send ByVal – but not always
possible with arrays in some
languages
Modules are self contained and then
can be reused in other programs he
wants to create without needing to
take the global variables with them
+ve Local = memory efficient
-ve Local = more difficult to
trace/debug/follow where the values
are passed
Global adv + dis
can be accessed from all modules by direct reference
might not be memory intensive,
unlikely anyone else is going to
access/amend e.g. use as a library –
therefore global would not waste
significant resources
Benefits:
* 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
easier programming,
simpler to follow, easier to debug
Drawback:
* Increases memory usage (as it is used until full program execution is over)
* Alterations within the function may have unwanted side effects elsewhere in
the program.
memory inefficient, not
good programming technique
IDE writing
- Auto-complete
- Start typing an identifier/command and it fills in the rest
- Auto-indent
- Indents code automatically within structures to avoid errors
- syntax highlighting
- Shows which commands are correct // help identify key elements
autocorrect - Tell you when you make a syntax error
IDE testing
- Breakpoints
- Stop the program running at a set point to check variables
- Variable watch window
- Display the values of the variables while the program is run
- Stepping
- Run one line at a time and check variables
Unit Testing
* Automated tests to be run to check changes ensure changes haven’t introduced errors.
IDE debugging
Underlines syntax errors dynamically
Can be corrected before running // saves times
Watch window
View how variables change during running of the program
Break points
Stop the program at set points to check the values of variables
Error message list
Tells you where errors are and suggests corrections
Step-mode
Executes program one statement at a time to watch variable values and program pathways
Traces
Print-outs of variable values for each statement execution within a program
Crash-dump/post-mortem routine
Shows the state of variables where an error occurs
Stack contents
Shows sequencing through procedures/modules
Cross-referencers
Identifies where variables/constants are used in a
program to avoid duplications
Reusable components
Saves time from having to write the same algorithm repeatedly
* Reduced testing requirements
* Can be taken and used in different programs as well as the program they are
written in // can be used in a program library
Breadth?
takes first value then visits all
nodes connected to it. It then takes all
nodes connected to those nodes.
more efficient when the data
searched for is closer to the root
Depth?
note same as post order
left node, this
becomes a new tree. It continues going to
the left until a leaf. It then returns this, then
goes right and repeats from the start. Follow
left, follow right, take root.
breath vs depth
Breadth is more efficient when the data
searched for is closer to the root.
* Depth is more efficient when data to be
search for is further down.
* Depth memory requirement is linear
* Depth can be written recursively to aid
understanding.
* Breadth in general is better time complexity
* In large trees depth may never return a
value
why use array instead of separate v?
all values can be indexed in one
array
* The numbers can be passed as a single parameter
* Does not need 50 variables to be declared/passed
Merge vs bubble vs insertion vs quick
Merge sort splits data into individual lists and merges
* Insertion makes first value sorted list, then inserts each item into the sorted list
* Bubble sort looks through each item in turn, number of items times
Merge uses more memory as new lists are needed. Insertion and Bubble need constant memory.
Quick increases not as much as merge
Best time:
* Bubble and Insertion have the best times, both O(n) because they run through data once. (increase at same rate as # elements)
Quick and merge increase at greater rate merge sort requires a minimum number of stages so best case is longer (O(n log(n))
* Merge average is the same as best.
Insertion and Bubble has average o(n^2).
Worst time: insertion and quick increase significantly by n for each additional item. O(n^2) for bubble + insertion
Merge sort increases less per
element - same number of stages
are needed.
When use bubble, merge, insertion, quick?
small number - bubble or insertion as no further space needed and tc small
merge may not need lots of memory too but timewise theyre all similar ish as small number - space not imp tho
large
Log more appropriate for large number
of elements
but memory imp although logarithmic more appropriate
Differences bet reality and simulation
Removal of visual elements such as buildings on the ground
* Simplification of controls
* Focus on important elements such as weather, height, speed
Why abstract?
Reduce memory requirements
* Reduce processing requirements
* Simplify the problem being solved
Reduces complexity of design
Reduces complexity of programming
Could involve a large number of images that would take
excessive memory
Reality contains things that aren’t relevant to a computer program
How use caching?
Store data that has been used in cache/RAM in case needed again
Directed vs undirected
ARCS/EDGES in 1 direction for directed
Graph vs tree
Graphs:
multiple paths
no (clear) root node
weighted (can be)
loops/cycles
bi-directional
tree has hierarchy
Both:
nodes, connected by edges, non-linear DS, dynamic
Visualisation
benefit humans rather than computers
present the information in a simpler form to understand
best explain complex situations
symbols
edges for physical connections bet addresses not actual physical routes
D vs A*
both pathfinding algos to find shortest route
A* is (usually) more efficient // dijkstra’s is (usually) slower
* A* uses heuristics to find a solution faster // Dijkstra’s does not use heuristics
Performance modelling?
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
Test with large and small values
* Model how well the system scales with increasing use
recursive func
A function that calls itself // a function that is defined in terms of itself
* …has a base case (that terminates the recursion)
use array for queue?
- 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
Describe OOP
defines an object as an independent
entity
defines the attributes of the object and
the methods that can be applied to it
attributes could be private to restrict
accidental changes
Many instances of can then be
declared in the main program without having to re-write all of the
declarations
reduces amount of code needed
fewer errors are likely as code is
written once and used multiple times
reduce mistakes because the
subroutines are self-contained
Describe procedural
statements are executed in
the order they are written
Procedural will need each queue to be
declared individually
* Procedural will need to make use of
subroutines where the queue will need to be
sent and returned each time.
have to write
separate code for each new
need to make sure the correct
values are passed and returned, or global
variables may be required which uses
excess memory.
how abstract?
remove unnecessary details
No actual images shown
Items are named / labelled
Simplified layout with shapes
e.g. simplify real life - remove complexity from realistic entities
represent _ with specific objects/shapes
remove outside world
remove character features - unneeded
if tree: represent _ w vertices
state represented by letter - tree doesn’t show details
Application of concurrent p?
- Multiple requests to the server can
be made at the same time - Programming on server will need
to allow multiple threads to
manipulate a list of requests - Programming will need to restrict
access to the database of
seats/sales etc. - Will allow those reading and writing
to manipulate at the same time - Record locking will need
implementing – more complex
programming - May be selling alongside other
systems, therefore needs to
communicate with external
systems that will also use record
locking to avoid two different
external companies accessing and
selling the same tickets. - Will allow for multiple access to the
website at the same time by
different customers – as it would
happen in real life
multiple ticket sales
for the same event without selling
the same seat twice
concurrent p?
Multiple processes being executed at the same time // appearing to happen simultaneously
* Giving processes a slice of the processor time
* Having multiple processors each carrying out a different process
- One process may need to start
before a second has finished - Individual processes are threads,
each thread has a life line - One request will be sent to the
server, this will have a thread
heuristics?
rule of thumb/estimate
estimates distance/cost from each node to destination n
speeds up finding solution as identify which paths first follow
h approach:
Rule of thumb/educated guess approach (1 –
AO1.1) which is used when unfeasible to analyse
all eventualities (1 – AO1.1).
This leads to a “good enough” result (1 – AO1.2)
although it is not 100% reliable
Data m - what is it
searches large amounts
of data
* Searches for relationships between
facts/components/events that may
not be obvious
* May include pattern matching
algorithms
* May involve anomaly detection
algorithms
* Used for business modelling
* Used to plan for future eventualities
Data m examples/application
- Can look for how people use the
website e.g. visiting times, what they
click on, how long they spend on
certain features, what they do first,
which elements are used least - Give recommendations for future
changes to the game e.g. features to
add, or remove - Can use to introduce new features
- Increase use from users
- Increase revenue by selling features
used more often - Make the game more appealing
- Remove features people don’t use
- Use to target advertising
- Privacy concerns from users
- Misuse of information
Quick sort
Choose a pivot // identify start and end pointers
* Compare each element to the pivot… // compare start and end pointers
* Put items < pivot in the left sublist
* Put items > pivot in the right sublist
* Choose a pivot in each sublist
* If start pointer is larger than end pointer…
* …then swap data items around
* And repeat the process until each item becomes a pivot
Why is quicksort divide and conquer
decomposing data sets into smaller subsets
* and then sorting each split subset
* until each subset is sorted
* and then combining the subsets to provide a solution
What IDE
why?
software that includes an
editor, compiler, run-time
environment
Allows you to write and run the code
in one piece of software
* Suggests code so you don’t have to
remember code, autocorrect
spelling
* Helps you trace the program so you
can see what happens when values
change without having to manually
insert print statements
* Autogenerate boilerplate code.
- Reduce errors through autocorrect
+ suggestions - Reduce time to write the program
because features help you spot
errors before running code,
some errors will be corrected so you
don’t have to - Write and test in one environment so
you don’t have to close and run
elsewhere, then re-open etc.
constructor?
create instance of object from class
inheritance
child class takes on attributes/methods from parent class
pipelining?
Reduces/removes latency
* … CPU is not idle while waiting for next instruction
* Next instruction is fetched while current one is decoded/executed
* All parts of the processor can be used at any instance in time
procedure of enqueue?
Check if the queue is full
* … if the firstElement pointer (+1) = lastElement
* … if it is return False
* Adds element at lastElement (+1) position
* … increments lastElement pointer
* If lastElement is greater than last Index // pointer becomes pointer MOD array.size
* …reset to 0
Why decompose?
Splits the problem into smaller sub p
* Smaller problems are more manageable & easier to solve
* To see where code can be reused in the solution
* To split tasks between different programmers - division lead to logical div bet programmers + dev of modules/subroutines
(repeated d - gives solvable parts)
Good as work concurrently on diff parts
Why decompose?
Splits the problem into smaller chunks
* Smaller problems are more manageable & easier to solve
* To see where code can be reused in the solution
* To split tasks between different programmers
Why not binary search tree?
more than 2 connections
nodes aren’t ORDERED
delete node from tree?
search tree to find nodes location
replace content of node w null
make node pointing to this point to one after
add new node to empty node list
add node?
search tree to find node adding after
create new node w value _
add pointer from prev to point to it
make new node null point to null
recursion vs iteration
Recursion uses more memory…
as declares new variables //variables are put onto the stack each time…
* can run out of memory/stack space…
- …iteration reuses the same variables - cannot run out of memory
- Recursion can express a problem more elegantly // in fewer lines of code…
- iteration can take more lines of code // be harder to understand
- Recursion will be self-referential // will call itself…
- … whereas iteration does not
why pass array by reference and not value?
By reference will change the actual contents of the array in the main program//
when control returns to the main program the array will be sorted
* By value would create a copy and not change the original // when control
returns to the main program the array will not be sorted
* By value the array is local to the func
reference uses less memory
bubble sort?
Compare each pair of adjacent elements
* If they are not in the correct order then swap the elements
* If they are in the correct order then do no swap elements
* When you read the end of the array return to the start
* Repeat n elements time
* Set a flag to be false whenever a swap is made
* …repeat the loop if the flag is not false
implement queue to circular w pointers?
- Check if either head or tail are incremented to above 99
- … set to be 0 instead
- When checking if array is full check if (queueTail == queueHead – 1) OR
(queueTail==99 AND queueHead==0)
add priorities to queue?
Use a different structure e.g. a linked list
* …items can be added at different points in the linked list depending on priority
* …by changing the pointers to items needing priority
* Have different queues for different priorities
* …add the job to the queue relevant to its priority
* …print all the jobs in the highest priority queue first
Set vs get method
A get method allows the attribute to be accessed / returned
* A set method allows the attribute to be changed (with parameters)
iteration vs recursion?
Benefit:
The program can/might run faster
Cannot run out of stack space/memory
Easier to trace/follow
Drawback:
Iteration can lead to lengthier code
Iteration can lead to code that looks more complex / is harder to
understand
some problems are more elegantly coded with a recursive
solution
Set vs get method
A get method allows the attribute to be accessed / returned
* A set method allows the attribute to be changed (with parameters)
insertion use less memory than merge?
erge 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.
data input?
number, name, location, dimensions of things
recognition
identify problem to be solved
data mining
Turning large quantities of data into useful information
/ Finding patterns within large quantities of
information
e.g. customer trends, profitable items
involves
searching through unconnected data (1), pattern
matching (1) and calculation of correlation (1).
There may be no predetermined matching criteria
(1); a brute force approach is possible with high
speed computers
performance modelling
simulate/test behaviour of system before used
e.g. stress testing - large customers or orders
reusbale c
the components can be used in a future programs + already tested
they do not need to be rewritten / saves time
record vs class
Record is a data structure…
…A class is a template for making data structures (objects)
Class also has methods (which describes functionality)
Both store data of different types
Which can be accessed by their names
But classes can make them accessible via methods
Both can have multiple ‘instances’
Class can include visibility of properties / private
record vs class
Record is a data structure…
…A class is a template for making data structures (objects)
Class also has methods (which describes functionality)
Both store data of different types
Which can be accessed by their names
But classes can make them accessible via methods
Both can have multiple ‘instances’
Class can include visibility of properties / private
how do private attributes improve data integrity
Properties (are encapsulated) and can only be accessed through their methods
Enforce validation through the method // inappropriate data can be caught before entered
Cannot be changed/accessed accidentally
ensure items and queue exists when the program is run next time?
Store the items and queue to an external file (when the program closes)
Load the items and queue from the file when it starts
depth vs breadth
Depth first advantage:
Depth first requires less memory than breadth first
search (1). It is quicker if you are looking at deep
parts of the tree (1).
Depth first disadvantage:
Depth first isn’t guaranteed to find the quickest
solution (1) and possibly may never find the
solution (1) if we don’t take precautions not to
revisit previously visited states
why is big o estimate?
Big O notation shows the limiting behaviour of an algorithm (to classify its complexity) (1).
Other processes may be taking up some of the
processor time
