# Shared Flashcard Set

## Details

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

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
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
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!