Use LEFT and RIGHT arrow keys to navigate between flashcards;
Use UP and DOWN arrow keys to flip the card;
H to show hint;
A reads text to speech;
34 Cards in this Set
- Front
- Back
|
Difference between sorted and unsorted list implementations of a PQ |
Sorted implementation has O(n) insertion time and O(1) removeMin time. Unsorted implementation has O(1) insert time and O(n) removeMin time. |
|
|
What are the three basic components that make up a priority queue? |
The entry, the comparator and the list. |
|
|
What is the difference between a priority queue and a queue? |
Queue is FIFO. Elements are added at the end of a queue. PQ stores entries. Entry with the highest priority is removed first. Priority is assessed through a comparator. |
|
|
What is Priority Queue "Selection Sort"? |
A PQ sort variation where the PQ is implemented with an unsorted sequence. Selection sort has O(n^2) runtime. |
|
|
What is PQ insertion sort? |
Variation of PQ sort where the PQ is implemented with a sorted sequence. Insertion sort has O(n^2) runtime. |
|
|
What is In-place Insertion sort? |
Instead of using a external data structure like Insertion and selection sort. In-place Insertion sort can be implemented without an external data structure. This is normally done through swapping elements until the entries are sorted. |
|
|
What are the main methods of a PQ ADT? What are the application of PQs? |
Insert(), removeMin(), min(), size(), isEmpty(). Applications of PQ: auctions, Stock markets, |
|
|
What is a heap ADT? |
A binary tree that has: -Heap-Order: for any node v. Key(v)>=key(parent(v)). -Last node of the heap is the right most node of max depth -Complete: The tree has 2^i nodes where i is the depth and height h=i-1 |
|
Is this a heap? |
Yes |
|
Is this a heap? |
Nope. The 1 violates heap order |
|
Is this a heap |
No. Does not fulfil the completeness, heap order and the last node requirements |
|
|
Can we use heaps to implement Priority Queues? |
Yes. |
|
|
During a down heap operation of a heap which child is swapped with the node? |
If the node has no right child the left one is picked. If the node has both a left and right child the childe with the smallest key is picked. |
|
|
What is an Adaptable Priority Queue? |
Priority queue that allows for the editing of entry keys and values. The runtime of remove() replaceKey() and replaceValue() differs according to implementation |
|
|
Compressed tries |
Pick a few words. Build compressed tries for those words and use the true to output a binary version of those words. |
|
|
Skipped list |
Write a set of insertion and remove +get instructions for a skipped list then implement them with pen and paper. Use a coin for RNG. |
|
|
What are the three algorithms for priority queue sorting? |
Selection sort, heap sort, and insertion sort. |
|
|
What is the runtime of insertion sort?(sorted list implementation of PQ) |
O(n^2) |
|
|
What is the selection sort runtime for a unsorted list implementation of a PQ |
O(n^2) |
|
|
What is the runtime of a sorting operation for a heap based implementation of a Priority Queue? |
O(nlogn) |
|
|
What is merge sort runtime? |
O(nlogn) |
|
|
What is the stable sort property? |
Relative order of two items with the same key is preserved |
|
|
Runtime of lexicographic sort |
O(d*T(n)) where d is the number of dimensions and T(n) is the sorting speed of the stable sorting algorithm |
|
|
What is radix sort? |
A specialised version of Lexi sort. Uses backer sort as the stable sorting algorithm. Runs in O(d*(n+N)) |
|
|
What are the properties of a 2-4 tree? |
2-4 trees are multi-way search trees that fulfill: Node size property: All internal nodes have 4 children. Depth proptlerty: all external nodes have the same depth. |
|
|
How many items are there in a 2-4tree of height h |
n=2^h-1 h<=log(n+1) |
|
|
What are (a,b) trees? |
They are multi-way trees which have the following properties: Size property: Each internal node has at least "a" children and at most b children. Depth property: All external nodes have the same depth. "a" and b are such that: 2 <= a<= (b+1) / 2 |
|
|
What is the height of an (a,b) tree storing n entries? |
At least Log_a (n) At most Log_b(n) |
|
|
What is a splaying? |
The rotation of a node to the root performed after search,insert and remove operations of as play tree. |
|
|
What's the runtime cost of splaying? |
O(h) where h is the height of the tree. |
|
|
What properties does a binary need to have to be called a red-black tree? |
Root Property: root is black. External Property:every leaf is black. Internal Property: children of a red node are black Depth Property: all trees have the same black depth |
|
|
What are the two heuristic exploited by the boyer Moore pattern matching algorithm? |
Looking glass heuristic Character jump heuristic |
|
|
Explain the looking glass heuristic |
|
|
|
Explain the character jump heuristic |
|
