Term
Begin with the vector v = [ 50 , 20 , 40 , 10 , 5 , 30 , 45] .
Show the vector after fsu::g_push_heap(v.Begin(), v.End()). |
|
Definition
| v = [ 50 , 20 , 45 , 10 , 5 , 30 , 40 ] |
|
|
Term
| COMPARISON SORT IS STABLE AND HAS BEST POSSIBLE WCRT? |
|
Definition
|
|
Term
| WHAT SORT IS STABLE, IN PLACE AND HAS BEST POSSIBLE WCRT? |
|
Definition
|
|
Term
Begin with the vector v = [ 50 , 30 , 40 , 5 , 10 , 20 ].
Show the vector after v.PushBack(45). |
|
Definition
| Correct Answer: |
v = [ 50 , 30 , 40 , 5 , 10 , 20 , 45 ] |
|
|
|
Term
| Code implementing merge_sort (A, p, r) for the index range [p,r)in the array is: |
|
Definition
void merge_sort(int* A, size_t p, size_t r)
{
if (r - p > 1)
{
q = (p+r)/2;
merge_sort(A,p,q);
merge_sort(A,q,r);
merge(A,p,q,r); // defined in separate function using g_set_merge
}
} |
|
|
Term
Define an edge move to be a call to any of the following fsu::TBinaryTree<>::Navigator operations: Initialize() (i.e., assignment to root), ++(), ++(int), --(), or --(int).
What, for a general binary tree, should the sum of all edge moves in an inorder traversal be? (n = size) |
|
Definition
|
|
Term
| (!) What is the theoretical lower bound on the worst case asymptotic runtime for comparison sorts? (n = size of input) |
|
Definition
|
|
Term
| The following sorts are stable |
|
Definition
Bit Sort
Radix Sort
Insertion Sort
Counting Sort
Merge Sort
|
|
|
Term
(!) You are given the following declarations:
fsu::TBinaryTree bt;
fsu::TBinaryTreeInorderIterator i;
Define an edge move to be a call to any of the following fsu::TBinaryTree<>::Navigator operations: Initialize() (i.e., assignment to root), ++(), ++(int), --(), or --(int). For the bt = tree1 illustrated, complete the table of numbers of edge moves on the exam paper, showing the number of edge moves for each step in an inorder traversal.
step no. of edge moves
---- -----------------
A
i = bt.Begin(); / \
B C
++i; / \
D E
++i;
[tree1]
++i;
++i;
++i;
The sequence of numbers of edge moves is: |
|
Definition
|
|
Term
| The worst case run time [WCRT] for TBinaryTree<>::Iterator::operator++() (where n = size of the tree) is: |
|
Definition
|
|
Term
| The run space requirement of Bit Sort (n = size of input) is |
|
Definition
|
|
Term
Define an edge move to be a call to any of the following fsu::TBinaryTree<>::Navigator operations: Initialize() (i.e., assignment to root), ++(), ++(int), --(), or --(int).
What does the calculation of the number of edge moves in a traversal illustrate about the computational complexity of the iterator increment operator fsu::TBinaryTreeInorderIterator<>::operator++() ? (n = size of tree) |
|
Definition
| That it is amortized Θ(1) |
|
|
Term
| Deriving the theoretical lower bound on the worst case asymptotic runtime for comparison sorts uses (select all that apply) |
|
Definition
The minimum height of a binary tree with N leaves
The number of permutations of n items
Stirling's Formula
A decision tree
|
|
|
Term
The run space requirement of Bit Sort (
n= size of input) is:
|
|
Definition
|
|
Term
| What is the theoretical lower bound on the worst case asymptotic runtime for comparison sorts? (n = size of input) |
|
Definition
|
|
Term
| The following comparison sort is stable and has the best possible worst case runtime: |
|
Definition
|
|
Term
Begin with the vector v = [ 50 , 30 , 40 , 5 , 10 , 20 ]. Show the vector after v.PushBack(45). |
|
Definition
v = [ 50 , 30 , 40 , 5 , 10 , 20 , 45 ]
|
|
|
Term
| The worst case run time [WCRT] for TBinaryTree<>::Iterator::operator++()(where n is the size of tree) is: |
|
Definition
|
|
Term
| Given the array a = [ F , G , A , H , B , D ] show the result of the first call to Partition in Quick Sort with the pivot value chosen to be the last element of the array. |
|
Definition
[ A , B , D , H , G , F ]
|
|
|
Term
|
Definition
A sort in which decisions are made based on key comparisons.
|
|
|
Term
| Deriving the theoretical lower bound on the worst case asymptotic runtime for comparison sorts uses (select all that apply) |
|
Definition
A decision tree
Stirling's Formula
The number of permutations of n
The minimum height of a binary tree with N |
|
|
