Comp 2 Flashcards
What is single processor concurrency?
A processor that processes sequentially but can switch very quickly between processes hence giving an impression of parallel processing.
What is multiprocessor concurrency?
- Processes can be processed concurrently
- Programs are broken down into sub programs and places in a queue to avoid synchronisation problems.
Advantages and disadvantages of multiprocessor concurrency?
Advantages:
- Increased speed as more then one process can be process at a time
- Utilised in divide and conquer algorithm
- Less wait time for input/output operation as during relevant processes can be executed
Drawbacks:
- Difficult to identify where it can be implemented in a program
- Harder to debug and test as some errors are time related
What is the main difference between functions and procedures?
Functions return values where as procedures generally do not.
Advantages of functions/procedures?
- Less code needs to be written as no need to repeat code
- Easier to read and understand when monitoring and fixing code
What is a parameter?
A parameter is an variable passed to a function.
What does it mean to pass a variable by reference?
- ByRef means that when the variable is passed it is passed by reference from memory.
- Any changes made are saved to memory.
What does it mean to pass a variable by value?
- By value means that any changes made to variable in the function is not saved in memory
Describe the four types of abstraction?
Procedural: Breaking problems into sub-problems
Functional: Utilising in-built functions from library
Data: Isolation how data is created and how it behaves
Problem: Problems removed until it’s straightforward and simple.
Describe a repeat until loop.
A repeat until loop is always executed at least once.
At the end of the program the condition is tested and repeats until no longer true.
Compare recursive solution to a iterative solution.
- Recursive solutions have fewer variables
- Harder to understand making it harder to maintain
What is a variable?
A space in memory that holds a value which can be changed during the execution of the program.
What is a local variable?
Local variables are variables only available to the function they are coded in.
What is a global variable?
A variable that is available to the whole program.
Compare the use of global and local variables?
Global should only be used if there is use of value throughout program as otherwise it hard to trace and uses up memory unnecessarily.
Local variables are more memory efficient as only take up memory when used.
Easy to trace as it promotes modularity.
Advantages of modularity?
- Breaking down a problem into sub-programs saves development time as more than one person can work on it at a time.
- Debugging and testing easier as less time spent locating errors
- Programs are easier to understand and maintain.
- Any new features are easy to add.
What are declarative languages?
A language which expresses structure and logic of computation without control flow.
What is backtracking?
When a programmer searched different logical pathways until the correct one is found. Trial and error approach.
What is Heuristics?
Rule of thumb/educated guess approach which is used when unfeasible to analyse
all eventualities.
This leads to a “good enough” result
although it is not 100% reliable
What is pipelining?
Next instruction being fetched even though current instruction is not yet finished executing.
What is caching?
Commonly used instructions stored in fast memory storage. Web pages can be stored this way.
What are the benefits and drawbacks of caching?
+ Reduces execution time as data can be accessed faster.
+ Faster then RAM
- Can produce stale data.
- Very expensive
- Small compared to RAM
What does a precondition consist of?
Name:
Input:
Output:
Precondition:
What are the advantages of preconditions?
Documentation helps maintain and understand the code.
User can know the checks that need to carried out before subroutine is called.
Explain the Dijkstra algorithm.
1) Select a start node
2) Give start node a value of 0 and all other nodes a value of infinity.
3) Place nodes into a queue.
4) Remove start node and neighbour node.
5) startNode = u & neighbourNode= w
6) newDistance = distanceAtU + distanceUToW
if newDistance < distanceAtW
distanceAtW = newDistance
7) Queue changes to reflect this
Describe what is meant by recursion.
The function calls itself from within the function.
Explain advantages of using reusable components.
- Modules already tested so more
reliable programs. - Less development time as programs
can be shorter and modules can be
shared
What are the three types of modelling?
- Physical
- Process
- Mathematical
Explain Physical modelling.
Real life objects represented as scale models to see how they behave in certain situations
Explain Process modelling.
Used to predict delays and physical limitations
Solution can be improved and changed the addition of more physical factors
Explain mathematical modelling.
Computer program runs a simulation modelling a situation
What is representational abstraction?
Unnecessary information removed leaving only information required to solve problem
What is generalisation abstraction?
Problem simplified by grouping similar parts into hierarchical structure.
What is function abstraction?
Exact computational method is hidden
What are sub-procedures?
Block of code that solves a small part of the problem/aim of the program.
What are the advantages of using sub-procedures?
- Use of sub-procedures aids readability and making main program appear less complex.
- Can be re-used in other parts of program
- Can be treated as object with own task
- Can be developed independently of other code
What is multi threading?
Technique where by particular section of code can be used by numerous processors at different stage of execution.
How does sequence structures work?
Program executes each statement or function in order.
How does branching/selection structure work?
Selection structure is where program executes different actions or statements on result of a comparison
What is an IDE?
An integrated development environment (IDE) provides a range of tools for a computer to develop high level language software.
What are the features of an IDE?
- Syntax highlighting
- Spell check
- Error diagnostics
- Source editor
- Break points
- Auto documentation
What is a class?
A class describes attributes and methods and is a template that can be used to create objects
What is an object?
Contains data and operations for a real world object.
- Instance of a class
What is encapsulation?
Combination of data and operation into an object
What is inheritance?
A sub class inherits the attributes and methods of a parent class.
What is polymorphism?
Permits different objects in a class to be process differently.
What are advantages of using OOP?
- Written using modules based on objects making it easy to follow and modify if needed
- Modular nature allows more then one person to work at same time
- New function added simply by creating new class or object
- Class only concerned with data within, unlikely to access any other data
- Data can be hidden within a class providing better security
- Inheritance makes code reusable and less code needed
What are advantages of decomposition?
- Breaking problem down into parts helps clarify what exactly needs to be achieved.
- Each break down makes problem easier to fix
- Some functions may be reusable
- Allows more then one person to work on it at the same time
Disadvantages of decomposition?
- Solutions to a problem may not combine to produce solution to initial problem
- A problem that is complex and misunderstood is difficult to breakdown.
What is data mining?
Analysing data to find patterns, trends and relationships
What is data warehousing?
Used in conjunction with data mining, combines data from different sources into comprehensive database that aids easy handling.
What is visualisation?
Technique where by visual model or image used to display problem and data.
What is the suitability, time complexity and space complexity of bubble sort?
Suitability:
- Requires little memory, useful in embedded system
- Only suitable for small data sets, as larger size takes longer
Time complexity:
- Most inefficient
- O(N^2)
Space complexity:
- O(1)
What is the suitability, time complexity and space complexity of insertion sort?
Suitability:
- Efficient for small data sets
- Faster then bubble sort for all data
- Takes longer with large data set
Time complexity:
- O(N^2)
Space complexity:
- O(1)
What is the suitability, time complexity and space complexity of merge sort?
Suitability:
- Divide and conquer algorithm suitable for large data sets
Time complexity:
- Fast O(N log(N))
Space complexity:
- O(N)
What is the suitability, time complexity and space complexity of quickSort?
Suitability:
- Efficient for any length of data
- Divide and conquer algorithm
Time complexity:
- O(N log(N))
Space complexity:
- O (Log(N))
What is the suitability, time complexity and space complexity of Dijkstra?
Suitability:
- Shortest distance between two points on map
Time complexity:
- Longer with more vertices
- O(E Log (V))
Space complexity:
- O (V + E)
What is the suitability, time complexity and space complexity of A* algorithm?
Suitability:
- Shortest distance between two points but faster
- Faster because of heuristics
Time complexity:
- O(E)
Space complexity:
- O(V)
What is the suitability, time complexity and space complexity of Linear Search?
Suitability:
- Can handle data that is unordered
- Can take long as it starts from beginning
Time complexity:
- O(N) (WORSt)
- O(N/2) (AVERAGE)
Space complexity:
- O(N)
What is the suitability, time complexity and space complexity of Binary Search?
Suitability:
- Data has to be in order
- Otherwise faster
Time complexity:
- O(Log (N)) (WORST)
- O(1) (BEST)
Space complexity:
- Iterative O(1)
- Recursive O(Log(N))
What are the features of Stacks?
- Used as temporary storage for functions and sub-routines
- LIFO
- Stores data not needed in function
What are features of Queue?
- Temporary storage of data (Buffer data)
- FIFO
What are features of Linked lists?
- Linear data structure
- Dynamic data structure
- Pointers link data elements
- Node = element in linked list
- Head pointer = Points to first node and head node
- Link = each node contains link detailing location of next node
- Null = Last node in linked list
What are features of a tree structure?
- Root = Starting node
- Parent = node in tree has nodes attached to it
- Child = node has single node above
- Leaf = Node has no node below it
What is a binary tree?
Tree structure where each node has no more then two child nodes.
What is depth first tree traversal?
Process for traversing tree data structure go left most sub tree until exhausted then move onto right sub tree.
What is breadth first tree traversal?
Start at root then move down each level.
What are the advantages and disadvantages of bubble sort?
Advantages:
- Useful when little memory required
- Easy to code, understand and implement
Disadvantage:
- Max (N-1) searches to fully sort
- Very time consuming for large data sets
What are the advantages and disadvantages of Insertion Sort?
Advantage:
- Simplest sort algorithm
- Efficient with small data sets
- More efficient then bubble sort
Disadvantage:
- Large number of element shifts required, if high number of elements performance decreases
What are the advantages and disadvantages of merge sort?
Advantage:
- Fast
Disadvantage:
- Uses additional temporary storage space to hold merged data, problem with long lists
What are the advantages and disadvantages of quick sort?
Advantage:
- Fast
- Little additional space is needed
Disadvantage:
- Choice of pivot directly affects performance
- Recursion partitioning hard to implement and code
What are the uses of Dijkstra algorithm?
- Determining shortest route between two places on map
- Determining shortest route for data packet in network
What is A* algorithm formula?
f(x) = g(x) + h(x)
x = last node on path g(x) = length of path from start node h(x) = heuristic function used to estimate distance from current node to goal node
