Paper 2 extra Flashcards
Describe how a leaf node is deleted from a binary search tree
Search/traverse tree until the required node is found
* Set the parent node pointer to the leaf node to null
* Add the deleted node to the free storage list // leave for garbage clear up
What is problem recognition
Problem recognition is identifying that there is a
problem to be solved, to determine exactly what the
problem is from a description/scenario and to
determine if the problem can be solved with
computational methods
What does problem recognition DO
Identify things
What does free list pointer do
Represents the next available space in the linked list
How is a value added to a linked list
Check to make sure freelist pointer is not null, add new data item to index (freelist pointer) , update free list pointer to location that new data item pointer is pointer at, update pointer from new data to null, update head pointer to indx of new data item (it depends basically if appending or prepending )
Final feature of recursive algo
Each recursive call will create a new copy of the values in the function….
* ….and add all of the values of the copy the call is being made from to a stack
What does big o measure
Number of steps and memory usage change according to amount of data as it increases
Linear
Grows in proportion to amount of data
Exponential
Rate of increase is at the rate k^n
Logarithmic
– means the rate of
increase gets smaller as the
amount of data increases time /
time increases at a rate of logkn
as n increases.
Advantages of concurrent processing (do not say allows more processes to be completed)
More efficient processor use // Less idle time for processor // Greater
throughput
* Long running tasks do not delay short running tasks
* Tasks requiring preconditions can wait and then resume execution
* User is able to interact with the computer while other tasks are running
Describe merge sort
The data list is split into two lists
* These sublists continue to be (recursively) split…
* …until each sublist is one item
* The first element in two different sublists is compared…
* …the smaller item is then selected…
* …and written to a new list
* …until both sublists fully merged
* Repeated until all sorted sublists are recombined
Benefits of merge sorts to bubble
More efficient time complexity (for large data sets) // takes fewer steps to sort
the data
* Time complexity O(n log n), rather than O(n2
)
- Uses divide and conquer
What can merge sort do that buble sort cant
Can apply concurrent processing to reduce sorting time
Drawbacks of merge compared to bubble
More difficult to implement // needs more complex code
* Less efficient space complexity // uses more memory with more data items
* Space complexity of O(n)/linear, rather than O(1) / constant
* Merge sort is always O(nlog2n) whereas the best case for bubble sort is O(n)
