Term
| For the selection problem, we want to get to the kth smallest element. If s is the first selected pivot, what happens after the first partitioning step? |
|
Definition
| If s > k, look for the kth smallest element in the left partition |
|
|
Term
| What defines a recurrence relation of some function R(n)? |
|
Definition
| value of R at some other point and an initial condition |
|
|
Term
| The recurrence for the sum of the first n integers is given by what? |
|
Definition
| S(n) = S(n-1) + n, S(0) = 0 |
|
|
Term
| Insertion sort takes time ______ in the average or worst case |
|
Definition
|
|
Term
| Topological sorting is based on _______ |
|
Definition
|
|
Term
| Binary search on a sorted array of n integers takes _____ time in worst case |
|
Definition
|
|
Term
| Given a balanced binary search tree of N integers, searching for an element can be considered an example of ____________ |
|
Definition
| decrease by a constant factor |
|
|
Term
| The worst case performance of quicksort for n items is _____ |
|
Definition
|
|
Term
| The worst case performance of mergesort for n items is _____ |
|
Definition
|
|
Term
|
Definition
|
|
Term
| Breadth-first search of a graph is best implemented using a ________ |
|
Definition
|
|
Term
| Which representation is best for a sparsely connected graph? |
|
Definition
|
|
Term
| Searching for an element in a hash table containing n elements takes _____ time |
|
Definition
|
|
Term
| The worst case complexity for searching for a value in an array is ______ |
|
Definition
|
|
Term
| Theta notation implies what? |
|
Definition
| That lower and upper bounds are the same |
|
|
Term
| What is the time for 10n^2 + 100n in theta notation? |
|
Definition
|
|
Term
| For the N item knapsack problem, the exhaustive search takes ______ time |
|
Definition
|
|
Term
| The convex hull of a triangle is _____ |
|
Definition
|
|
Term
| All operations of stack are ______ |
|
Definition
|
|
Term
| Most binary search tree algorithms typically run in time O(logN) if the tree is reasonably well balanced. What does N refer to? |
|
Definition
| The number of nodes in the tree |
|
|
Term
| Which representation is preferred for a densely connected graph? |
|
Definition
|
|
Term
| In analyzing algorithm, name the two most important resources of any algorithm |
|
Definition
| computation time, consumed storage |
|
|
Term
| 3 nested loops with each loop going from 1 through 1000 has complexity of ______ |
|
Definition
|
|
Term
| Big-O notation expresses what? |
|
Definition
|
|
Term
|
Definition
| a way to find the greatest common divisor of two positive integers |
|
|
Term
| For an algorithm for computing n!, what would be a natural size metric for its inputs? |
|
Definition
|
|
Term
| When finding the largest element in a list of n numbers (using the standard scanning algorithm), can the basic operation count be different for inputs of the same size? |
|
Definition
|
|
Term
| What is the basic operation of Euclid's algorithm? |
|
Definition
|
|
Term
| Informally, O(g(n)) is what? |
|
Definition
| the set of all functions with a lower or same order of growth as g(n) |
|
|
