Shared Flashcard Set

Details

Design & Analysis of Algorithms Exam 2
help me
22
Computer Science
Undergraduate 2
04/10/2017

Additional Computer Science Flashcards

 


 

Cards

Term
Decrease and Conquer
Definition
based on exploiting the relationship between a solution to a given instance of a problem and a solution to its smaller instance
Term
What is the complexity of insertion sort?
Definition
theta(n^2)
Term
Insertion Sort
Definition
to sort array A[0..n-1], sort A[0..n-2] recursively and then insert A[n-1] in its proper place among the sorted A[0..n-2]
Term
Topological Sort
Definition
Vertices of a dag can be linearly ordered so that for every edge its starting vertex is listed before its ending vertex
Term
Source removal algorithm
Definition
Repeatedly identify and remove a source (a vertex with no incoming edges) and all the edges incident to it until either no vertex is left (problem is solved) or there is no source among remaining vertices (not a dag)
Term
What is insertion sort good for?
Definition
Sorting small arrays or subarrays, or almost-sorted arrays
Term
How is insertion sort different from other sorting algorithms?
Definition
it has a faster average case than other elementary sorting algorithms and excellent efficiency on almost-sorted arrays
Term
What complexity does binary search on sorted lists have?
Definition
log2n
Term
Digraph
Definition
a graph with directions specified for all its edges
Term
Topological sorting
Definition
whether we can list a graph's vertices in such an order that for every edge in the graph, the vertex where the edge starts is listed before the vertex where the edge ends.
Term
selection problem
Definition
The problem of finding the kth smallest element in a list of n numbers
Term
What is the best case efficiency of Quickhull?
Definition
omega(n)
Term
Which of the three classic traversal algorithms yields a sorted list if applied to a binary search tree?
Definition
Inorder
Term
Preorder traversal
Definition
Visit the root before visiting the left, then right subtrees
Term
Inorder traversal
Definition
Visit the left subtree, the root, then the right subtree
Term
Postorder
Definition
Visit the left subtree, the right subtree, then the root
Term
stable algorithm
Definition
an algorithm where two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted
Term
Arrays composed of equal elements are the ______ case for quicksort
Definition
best.
Term
Strictly decreasing arrays are the ______ case for quicksort
Definition
worst
Term
For quicksort with the median-of-three pivot selection, strictly increasing arrays are the ______ case
Definition
best.
Term
For quicksort with the median-of-three pivot selection, strictly decreasing arrays are the ______ case
Definition
best.
Term
variable size decrease algorithm
Definition
works by reducing the problem to a smaller size
Supporting users have an ad free experience!