Term
| All operations on stack are _______ |
|
Definition
|
|
Term
Most of Binary Search Tree algorithms(like insertion, search)
typically run in time O( log N), if the tree is reasonably well
balanced. What does N refer to? |
|
Definition
| The number of nodes in the tree |
|
|
Term
|
Definition
| a simpler/more convenient instance of the same problem |
|
|
Term
| Breadth-first search of a graph is best implemented using what? |
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
| a different representation of the same instance |
|
|
Term
| Searching for an element in a hash table containing n elements can be performed in time ________ |
|
Definition
|
|
Term
|
Definition
| a different problem for which an algorithm is already available |
|
|
Term
| in analyzing algorithms, what are the two most important resources of any algorithm? |
|
Definition
| computation time and consumed storage |
|
|
Term
|
Definition
| a binary search tree in which, for every node, the balance factor is at most 1 |
|
|
Term
| 3 nested loops with each going from 1 through 100 has a complexity of _______ |
|
Definition
|
|
Term
|
Definition
| the difference between the heights of left and right subtrees |
|
|
Term
| What does big-O notation express? |
|
Definition
|
|
Term
|
Definition
| a similar idea to AVL trees in which the height of subtrees is allowed to differ by up to a factor of two |
|
|
Term
| Search, insertion, and deletion on AVL trees are ______ |
|
Definition
|
|
Term
| Searching, insertion, and deletion on binary search trees have worst case efficiency _________ |
|
Definition
|
|
Term
| Searching, insertion, and deletion on binary search trees have average case efficiency _________ |
|
Definition
|
|
Term
|
Definition
| a similar idea to AVL trees in which the height of subtrees is allowed to differ by up to a factor of two |
|
|
Term
| Search, insertion, and deletion on AVL trees are ______ |
|
Definition
|
|
Term
| Searching, insertion, and deletion on binary search trees have worst case efficiency _________ |
|
Definition
|
|
Term
| Searching, insertion, and deletion on binary search trees have average case efficiency _________ |
|
Definition
|
|
Term
| What is the efficiency of Gaussian elimination? |
|
Definition
|
|
Term
| Element uniqueness efficiency with brute force algorithm? |
|
Definition
|
|
Term
| Element uniqueness efficiency with presorting-based algorithm? |
|
Definition
|
|
Term
| Searching efficiency with presorting? |
|
Definition
|
|
Term
| ________ comparisons are necessary in the worst case to sort a list of size n by any comparison-based algorithm |
|
Definition
|
|
Term
| 3 nested loops with each loop going from 1 through N has a complexity _______ |
|
Definition
|
|
Term
|
Definition
| a search tree that allows more than one key in the same node of the tree |
|
|
Term
|
Definition
| a node of a search tree that contains n-1 ordered keys |
|
|
Term
|
Definition
| a search tree that may have 2-nodes and 3-nodes, and is height-balanced |
|
|
Term
| Search, insertion, and deletion of 2-3 trees are in |
|
Definition
|
|
Term
|
Definition
| a binary tree with keys at its nodes such that it is essentially complete, and the key at each node is greater than or equal to keys at its children |
|
|
Term
| heapsort stage 1 worst case efficiency? |
|
Definition
|
|
Term
| heapsort stage 2 worst case efficiency? |
|
Definition
|
|
Term
| heapsort stage 2 average case efficiency? |
|
Definition
|
|
Term
|
Definition
| the ADT of a set of elements with numerical priorities with operations to find element with highest priority, delete element with highest priority, and insert element with assigned priority |
|
|
Term
| All cases of mergesort have efficiency _________ |
|
Definition
|
|
Term
| mergesort space requirement? |
|
Definition
|
|
Term
|
Definition
|
|
Term
| Quicksort best case efficiency? |
|
Definition
|
|
Term
| Quicksort worst case efficiency? |
|
Definition
|
|
Term
| Quicksort average case efficiency? |
|
Definition
|
|
Term
| Quicksort best case efficiency? |
|
Definition
|
|
Term
| Quicksort worst case efficiency? |
|
Definition
|
|
Term
| Quicksort average case efficiency? |
|
Definition
|
|
Term
|
Definition
| smallest convex set that includes given points |
|
|
Term
| Insertion sort worst case efficiency? |
|
Definition
|
|
Term
| Insertion sort average case efficiency? |
|
Definition
|
|
Term
| Insertion sort best case efficiency? |
|
Definition
|
|
Term
| Is insertion sort stable? |
|
Definition
|
|
Term
| What is the best elementary sorting algorithm overall? |
|
Definition
|
|
Term
|
Definition
| a directed graph with no cycles |
|
|
Term
|
Definition
| when vertices of a dag are linearly ordered so that for every edge, its starting vertex is listed before its ending vertex |
|
|
Term
|
Definition
| a vertex with no incoming edges |
|
|
Term
| binary reflected gray code |
|
Definition
| minimal-change algorithm for generating 2^n bit strings corresponding to all the subsets of an n-element set where n>0 |
|
|
Term
| decrease-by-constant-factor algorithm |
|
Definition
| instance size is reduced by the same factor |
|
|
Term
| ________ is optimal for searching a sorted array |
|
Definition
|
|
Term
|
Definition
| a continuous counterpart of binary search for solving equations in one unknown f(x) = 0 |
|
|
Term
| decrease-by-constant-factor algorithm |
|
Definition
| instance size is reduced by the same factor |
|
|
Term
| ________ is optimal for searching a sorted array |
|
Definition
|
|
Term
|
Definition
| a continuous counterpart of binary search for solving equations in one unknown f(x) = 0 |
|
|
Term
| Efficiency for selection problem if sorted by mergesort? |
|
Definition
|
|
Term
| Average case efficiency of quickselect? |
|
Definition
|
|
Term
| worst case efficiency of quickselect? |
|
Definition
|
|
Term
| worst case efficiency of interpolation search? |
|
Definition
|
|
Term
| ___________ is preferable to binary search only for very large arrays/expensive comparisons |
|
Definition
|
|
Term
| worst case efficiency for searching in BST? |
|
Definition
|
|
