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
Breadthfirst 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 bigO 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 presortingbased 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 comparisonbased 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 n1 ordered keys 


Term

Definition
a search tree that may have 2nodes and 3nodes, and is heightbalanced 


Term
Search, insertion, and deletion of 23 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
minimalchange algorithm for generating 2^n bit strings corresponding to all the subsets of an nelement set where n>0 


Term
decreasebyconstantfactor 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
decreasebyconstantfactor 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

