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 you make a recursive call but don’t do anything with the result.
Explain priority queue.
A collection of prioritized elements. Allows the removal of element that has the first priority. When inserting user must provide a priority.
Can multiple elements have the same key in a priority queue?
Yes.
How are values stored in a 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 an Unsorted Priority Queue.
Create new PQEntry composite add that entry to the end of the list.
Explain insertion into a Sorted Priority Queue.
Create new PQEntry composite, find the appropriate position in the queue and insert it there.
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 and binary heap priority queue? Hence state + and - of each.
Unsorted:
Insertions O(1)
Min O(N)
removeMin O(N)
Sorted:
Insertions O(N)
Min O(1)
removeMin O(1)
Binary Heap:
Insertions O(log N)
Min O(1)
removeMin O(log N)
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 + 1) where h is 1-indexed
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.
Define the priority queue ADT.
A collection of prioritized elements. Allows the removal of element that has the first priority. When inserting user must provide a priority.
ADT functions:
size()
isEmpty()
insert(k, v)
min()
removeMin()
Explain the array representation of a heap.
Let j be the index of a position p.
Position of root is 0.
Position of left child of p = 2j + 1
Position of right child of p = 2j + 2
Position of parent of p = (j - 1) / 2
Explain insertion into heap. Explain as part of this upheap.
Add to end of array, or at the next free node in the tree from the left of the bottom level. If heap order is violated, parent(p).priority should be after p.priority then we swap p with its parent. And we keep doing so until the heap order is satisfied or p is the root.
Explain deletion from heap. Explain as part of this downheap.
Switch node to be deleted with last node. Then we can simply remove last node. Then we must restore heap property by downheaping the switched node. If heap order is violated, p.priority should be after the priority of its children then we swap p with its child that has the smallest priority. And we keep doing so until the heap order is satisfied or p is a leaf.
What is the time complexity for a heap (same as binary heap priority queue) for insertion, deletion, fast construction, slow construction and get.
insertion = O(log n)
deletion = O(log n)
fast construction = O(n) bottom up
slow construction = O(nlog n) top down
get = O(1)
Pseudocode for treeSearch.
treeSearch(Position p, Key k)
if(isExternal p){return p}
if(p.key = k){return p}
else if (k > p.key){return treeSearch(p.right, key)}
else {return treeSearch(p.left, key)}
