Paper 2 Flashcards
Describe the differences between queues and stacks
Stacks use LIFO whereas Queues use FIFO
Stacks have one top pointer, queues have one front and one back pointer
Stacks have push, pop and peek built in functions
Queues have functions to rearrange pointers when an item is removed or added
Describe the differences between functions and procedures
Functions have to return a value whereas procedures are unlikely to return any value,
Describe how bubble sort works
- go through array, comparing each item with the one next to it, If it is greater, swap them
- Repeat n-2 times
Describe how insertion sort works
The algorithm takes one data item from the list and places it in the correct location in the list and this process is repeated until there are no more unsorted data items in the list
Describe how merge sort works
- Divide the unsorted list into n sublists, each containing one element
- Repeatedly merge sublists in order to produce new sorted sublists until there is only one sublist remaining
What is the time complexity of bubble sort?
O(n^2)
What is the time complexity of insertion sort?
O(n^2)
What is the time complexity of merge sort?
O(nlog n)
Describe the orders of traversal for trees
Draw an outline around the tree structure from left to root and follow the path
Pre-order traversal - as you pass to the left of the node
In-order traversal - as you pass underneath a node
Post-order traversal - as you pass to the right of a node
What are the three essential characteristics of recursion?
- Stopping condition
- Routine must call itself
- Stopping conditions must be reached after a finite number of calls
Describe the steps in Dijkstra’s algorithm
- Set all distances to ifinity apart from starting node
- Pick first node and calculate distances to adjacent nodes
- Pick next node with minimal distance; repeat adjacent node distance calculations and overwrite if value is smaller than original
- Final result can be found from following the parent table
What is abstraction?
The separation of the physical and logical aspects of a problem where all details that doesn’t directly contribute to the problem at hand are ommited
Describe cashing
The temporary storage of data and instructions
- Faster access to cached resources
- Saves on costly use of bandwidth
- Reduces load on web services in a client-server environment
- Slower performance if the resource isn’t found
- Could be given an outdated resourse
Describe data mining
Data mining is the process of digging through big data sets to discover hidden connections and predict future trends, typically involving the use of different kinds of software packages
Describe the advantages of data mining
Helps marketing companies build models based on historical data to predict who will respond to the new marketing campaigns leading to an increase in profits
Helps government agencys by digging and analyzing records of financial transactions to build patterns that can detect money laundering or criminal activites
