# Shared Flashcard Set

## Details

Design & Analysis of Algorithms Quiz 2
I'm probably going to fail lol
67
Computer Science
03/23/2017

Term
 All operations on stack are _______
Definition
 O(1)
Term
 Most of Binary Search Tree algorithms(like insertion, search) typically run in time O( log N), if the tree is reasonably wellbalanced. What does N refer to?
Definition
 The number of nodes in the tree
Term
 instance simplification
Definition
 a simpler/more convenient instance of the same problem
Term
 Breadth-first search of a graph is best implemented using what?
Definition
 queue
Term
 a
Definition
Term
 representation change
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
 O(1)
Term
 problem reduction
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
 AVL tree
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
 O(1)
Term
 balance factor
Definition
 the difference between the heights of left and right subtrees
Term
 What does big-O notation express?
Definition
 upper bounds
Term
 red-black trees
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
 O(log n)
Term
 Searching, insertion, and deletion on binary search trees have worst case efficiency _________
Definition
 theta(n)
Term
 Searching, insertion, and deletion on binary search trees have average case efficiency _________
Definition
 theta(log n)
Term
 red-black trees
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
 O(log n)
Term
 Searching, insertion, and deletion on binary search trees have worst case efficiency _________
Definition
 theta(n)
Term
 Searching, insertion, and deletion on binary search trees have average case efficiency _________
Definition
 theta(log n)
Term
 What is the efficiency of Gaussian elimination?
Definition
 theta(n^3)
Term
 Element uniqueness efficiency with brute force algorithm?
Definition
 O(n^2)
Term
 Element uniqueness efficiency with presorting-based algorithm?
Definition
 theta(n log n)
Term
 Searching efficiency with presorting?
Definition
 theta(n log n)
Term
 ________ comparisons are necessary in the worst case to sort a list of size n by any comparison-based algorithm
Definition
 n log2 n
Term
 3 nested loops with each loop going from 1 through N has a complexity _______
Definition
 O(n^3)
Term
 multiway search tree
Definition
 a search tree that allows more than one key in the same node of the tree
Term
 n-node
Definition
 a node of a search tree that contains n-1 ordered keys
Term
 2-3 tree
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
 theta(log n)
Term
 heap
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
 theta(n)
Term
 heapsort stage 2 worst case efficiency?
Definition
 theta(n log n)
Term
 heapsort stage 2 average case efficiency?
Definition
 theta(n log n)
Term
 priority queue
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
 theta (n log n)
Term
 mergesort space requirement?
Definition
 theta(n)
Term
 pivot
Definition
 partitioning element
Term
 Quicksort best case efficiency?
Definition
 theta(n log n)
Term
 Quicksort worst case efficiency?
Definition
 theta(n^2)
Term
 Quicksort average case efficiency?
Definition
 theta(n log n)
Term
 Quicksort best case efficiency?
Definition
 theta(n log n)
Term
 Quicksort worst case efficiency?
Definition
 theta(n^2)
Term
 Quicksort average case efficiency?
Definition
 theta(n log n)
Term
 convex hull
Definition
 smallest convex set that includes given points
Term
 Insertion sort worst case efficiency?
Definition
 theta(n^2)
Term
 Insertion sort average case efficiency?
Definition
 theta(n^2)
Term
 Insertion sort best case efficiency?
Definition
 theta(n)
Term
 Is insertion sort stable?
Definition
 Y
Term
 What is the best elementary sorting algorithm overall?
Definition
 insertion sort
Term
 DAG
Definition
 a directed graph with no cycles
Term
 topological sorting
Definition
 when vertices of a dag are linearly ordered so that for every edge, its starting vertex is listed before its ending vertex
Term
 source
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
 binary search
Term
 bisection method
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
 binary search
Term
 bisection method
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
 theta(n log n)
Term
 Average case efficiency of quickselect?
Definition
 theta(n)
Term
 worst case efficiency of quickselect?
Definition
 theta(n^2)
Term
 worst case efficiency of interpolation search?
Definition
 C(n)=n
Term
 ___________ is preferable to binary search only for very large arrays/expensive comparisons
Definition
 interpolation search
Term
 worst case efficiency for searching in BST?
Definition
 C(n)=n
Supporting users have an ad free experience!