Term
|
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
|
|
Term
|
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
|
Definition
| Vertices of a dag can be linearly ordered so that for every edge its starting vertex is listed before its ending vertex |
|
|
Term
|
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
|
|
Term
|
Definition
| a graph with directions specified for all its edges |
|
|
Term
|
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
|
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
|
|
Term
| Which of the three classic traversal algorithms yields a sorted list if applied to a binary search tree? |
|
Definition
|
|
Term
|
Definition
| Visit the root before visiting the left, then right subtrees |
|
|
Term
|
Definition
| Visit the left subtree, the root, then the right subtree |
|
|
Term
|
Definition
| Visit the left subtree, the right subtree, then the root |
|
|
Term
|
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
|
|
Term
| Strictly decreasing arrays are the ______ case for quicksort |
|
Definition
|
|
Term
| For quicksort with the median-of-three pivot selection, strictly increasing arrays are the ______ case |
|
Definition
|
|
Term
| For quicksort with the median-of-three pivot selection, strictly decreasing arrays are the ______ case |
|
Definition
|
|
Term
| variable size decrease algorithm |
|
Definition
| works by reducing the problem to a smaller size |
|
|
