Week 6 + 7 Flashcards
Define f(n) is O(g(n)).
True if and only if there are positive constants c and n0 such that f(n) <= cg(n) >= foralln >= n0
What is memoisation?
A technique to speed up algorithms by keeping track of the result of an expensive operation, and returning just the cached result if the same operation is called again. Lookup table.
Define recursion.
The process of solving a problem by reducing it to smaller versions of itself is called recursion.
Explain the different types of recursion.
Linear Recursion: The function calls itself once per iteration, until it hits the termination condition. E.g. Factorial
Binary Recursion: When a function makes two recursive calls. E.g. fibonacci
Multiple Recursion: When a function makes two or more recursive calls. E.g. Inorder traversal
Mutual Recursion: Involves one of more functions which are calling each other.
Nested Recursion: Nested recursive calls where the function is called, and the result is passed to another call of the same recursive function. E.g. John McCarthy 91 function.
Tail Recursion: Tail recursion is a specialized form of the linear recursion where the
last operation of the function
happens to be a recursive call. I.e. Recursive call easily replaced with loop.
Explain priority queue.
Rank processes based on their worth and need for processor time. Processes with a higher priority will also receive a longer time slice.
Can multiple elements have the same key in a priority queue?
Yes.
How are values stored in priority queue?
Represented as composites using instances of the inherited PQEntry class (to contain a key and a value). These are stored in a double linked list.
Explain insertion into a Priority Queue.
Create new PQEntry composite add that entry to the end of the list.
How do we find the entry with highest priority in an unsorted priority queue?
Linear search.
What is the time complexities for unsorted priority queue in comparison to sorted priority queue? Hence give state + and - of each.
Unsorted:
Insertions O(1)
Min O(N)
removeMin O(N)
Sorted:
Insertions O(N)
Min O(1)
removeMin O(1)
Unsorted faster insertion, sorted faster removal.
What is the time complexity of PQ Sort on a standard Priority Queue? Discuss differences between sorted and unsorted?
O(n^2)
with sorted the INSERTION takes longer with unsorted the SELECTION takes longer but both end up with the same time complexity for PQ Sort.
What is the maximum number of nodes in binary tree of height h? How many levels does a tree of n nodes require?
2^h - 1
log2(n)
Define a complete binary tree.
One where every level (except possibly the last) is completely full, and the last level of the tree is filled from left to right.
Define the heap invariant.
Every value in both the left and right subtrees of a node must be less than or equal to the value at the node. Both the left and right subtrees must be valid heaps.
Tree is complete as defined above.
