paper 2 Flashcards
representational abstraction
removing excessive details to arrive at representation of a problem with only the key features
abstraction by generalization
grouping together similarities in a problem to better understand the issue, allows better categorization and the application of common solutions
data abstraction
nuisances in data are hidden to allow the application of common data structures, without focusing on the details of data
procedural abstraction
using functions and library without knowledge of how the code is implemented - used in psudeocode and decomposition as procedures are reused as black boxes
multilevel abstraction
in complex problems - highest levels of abstraction are closest to user, responsible to interface - lowest levels responsible for performing functions through execution
non expert use of abstraction
hide complex or irreverent parts to allow more people to understand code
design uses of abstraction
allows for more efficient designs - allows developers to focus on necessary elements rather than worrying about the details - prevents program from becoming too large and wasting development time
layers of abstraction in programming
lower level languages difficult to write, abstracted to high level languages it is easier to write as it is closer to english
levels of abstraction in networking
TCP/IP abstracts data transition into 4 parts - makes them simpler to program and understand - layers are independent but must return a common format
caching
storing commonly used instructions and data in ultra fast memory in, on or next to the CPU - decreases fetch time - common on commonly used web pages
prefetching
an advanced form of caching, algorithms predict what is likely to be fetched soon and loads it to cache - decreases idle time whilst waiting for fetch
limitation of caching
- prefetching can fetch wrong item clogging up RAM and offering no benefit
- effectiveness depends on cache algorithm
- large caches take a long time to search
- difficult to implement
reusable program components
commonly used functions and procedures are commonly packaged as libraries - allows reuse without rewriting functions
+ promotes more efficient design as procedures are planned and packaged before hand
+ increased reliability - better testing and bugs encountered sooner
+ saves time money and resources + reused in other projects
-can cause compatibility issues when using third party libraries - requiring refactoring of code
recursion
where a subroutine calls itself until a certain condition is met - same result as iteration but suits some problems better
+ fewer lines of code - less prone to errors
- can create infinite loop if end condition never met
call stack
each time a recursive function is called a stack frame is added to the call stack containing the parameters, local variables and a return address - allows the subroutine to return to a given point when complete - once the stop condition is met the subroutine unwinds through the stack frame
disadvantages of recursion
- inefficent use of memory
- can cause stack overflow if called to many times
- difficult to trace
scope
the section of code a variable can be referenced in
local scope
variables with limited scope - only accessed in certain blocks of code - multiple variables of the same name can coexist in different sub routines - good practice to make sure subroutines are self contained
global variables
variables accessible by the whole program - variables declared in the main function automatically set to global scope - not recommended as they can be unintentionally overwritten or edited - requires more memory as only deleted when program terminates not subroutine
modular programming
spliting large programs into smaller self-contained reusable modules - increases readability, simplifies testing and maitenance
top-down approach / step wise refinement
problem is continually broken down into sub problems until each can be represented as a single self contained black box subroutines, either functions or procedures
procedures
a named subroutine which performs a specific task - it does not have to return a value but can return multiple - typically uses parameters for manipulation data points
functions
a named subroutine that performs a specific task - must return one and only one value - commonly uses local variables for manipulation of data points
parameters passed by value
a copy of the value is passed and treated as a local variable, it is discarded once the subroutine is completed - it odes not effect values outside of the subroutine
parameters passed by reference
the address of the parameter is given to the subroutine - changes the value of variables outside and inside of the subroutine
IDE
Integrated Development Environment - a program which provides a set of tools to make development easier to write, read and debug - common features:
- stepping - allows monitoring of the effect of each line by executing one line at a time
- breakpoints - stopping the execution of a program at a set point based on a condition or line number - can pinpoint errors
- variable watch - observer how variables change during execution to pinpoint errors
- source code editor - provides auto-complete, indentations, syntax highlighting, and automatic bracket and quote completion
- debugging tools - run time error detection, with guides on where / how they are likely to occur and how to fix them
class
a template for an object, defining its states and behaviors - states are defined by attributes, giving each object its property - behaviors are defined by methods which describe the actions that can be performed
initilisation
the process of creating an object by calling the constructor method of a class, often used to set the attributes of that instance - multiple objects of the same class can exist simultaniously
encapsulation
attributes and methods can be set to public or private - public methods and attributes can be manipulated outside of the object - private methods and attributes can only be manipulated by other methods within an object - prevents accidental editing
performance modeling
eliminates the need for true performance testing by using mathematical methods to test a variety of loads on different OS - cheaper less time consuming and safer method of testing - used in safety-critical applications and systems, where trial runs are not safe - used to judge capability’s of systems in different environments
visulisation
presenting data in an easy to understand way - allows the identification of trends easier - can be done using graphs, trees, charts and tables
stacks
First in First out - dynamic not mutable - implemented as array - uses a single top pointer to indicate the item at the top of the stack - initialized at -1 so first item has index of 0 - operations:
- size() - returns top pointer + 1
- isEmpty() - checks if top pointer < 0
- peek() - returns top elements without removing it
- push(element) - adds element to stack and increments top pointer
- pop() - removes top item and returns it + decrementing top poiner
queues
First in first out - dynamic not mutable - implemented as array - two pointers - front pointer indicates first item - back pointer indicates next available space - operations:
- size() - returns number of items in queue by FP - BP
- isEmpty() - returns true if FP = BP
- peek() - returns front item without removing it
- enqueue(element) - adds element to queue at BP location then increments BP by 1
- dequeue() - item at FP is removed from queue and returned FP incremented by one
Linked lists
a series of non consecutive nodes, each containing a data item and a pointer to the location of the next item - mutable and dynamic - first item = head - last item = tail - can only be searched by a full traversal
trees
an abstract data type made up of nodes (data items) and edges (connecting nodes)
post order traversal
starting at the left-most leaf node each node is visited after both of its children such that the root node is visited last - used to get postfix expression of a tree and delete it
breadth first traversal
from the left the start node is visited then all of its children before all of their children and so on - used in dijkstras and A* - uses a queue
