Shared Flashcard Set

Details

Design & Analysis of Algorithms Final
AHHHHHHH
29
Computer Science
Undergraduate 2
05/04/2017

Additional Computer Science Flashcards

 


 

Cards

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
theta(n^2)
Term
Topological sorting is based on _______
Definition
DFS
Term
Binary search on a sorted array of n integers takes _____ time in worst case
Definition
theta(logn)
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
O(n^2)
Term
The worst case performance of mergesort for n items is _____
Definition
O(nlogn)
Term
Heaps are _______ trees
Definition
complete
Term
Breadth-first search of a graph is best implemented using a ________
Definition
queue
Term
Which representation is best for a sparsely connected graph?
Definition
Adjacency list
Term
Searching for an element in a hash table containing n elements takes _____ time
Definition
O(1)
Term
The worst case complexity for searching for a value in an array is ______
Definition
O(n)
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
Theta(n^2)
Term
For the N item knapsack problem, the exhaustive search takes ______ time
Definition
Omega(2^n)
Term
The convex hull of a triangle is _____
Definition
the triangle itself
Term
All operations of stack are ______
Definition
O(1)
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
Adjacency matrix
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
O(1)
Term
Big-O notation expresses what?
Definition
Upper bounds
Term
Euclid's algorithm
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
the magnitude of n
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
no.
Term
What is the basic operation of Euclid's algorithm?
Definition
modulo division
Term
Informally, O(g(n)) is what?
Definition
the set of all functions with a lower or same order of growth as g(n)
Supporting users have an ad free experience!