Show:
Complexity
Hash Tables
Priority Queues
Graphs
Sorting
100
Runtime independent of problem size.
What is constant run time or O(1)?
100
When your hashtable becomes too full, you perform this operation.
What is rehashing.
100
Mergeable queue which always swaps kids.
What is a skew heap.
100
A node in an undirected graph which causes the graph to become disconnected when removed.
What is an articulation point?
100
Property that records with the same key are kept in the original order by the sort.
What is stable?
200
When problem size doubles, run time doubles?
What is linear complexity or O(n)?
200
Linear probing results in this type of clustering.
What is primary clustering.
200
Is log n for insert, findmin, deletemin, and merge.
What is binomial queue?
200
timing for all pairs shorted path
What is O(n^3)?
200
Sort is also known as a diminishing increment sort.
What is shell sort?
300
When problem size doubles, run time increases by a factor of 8.
What is O(n^3)
300
Keys that hash to same location continue to compete for same subsequent hash locations.
What is secondary clustering.
300
Has log n amortized time for most operations.
What is skew heap?
300
A path in the network flow algorithm.
What is augmenting path?
300
In Timsort, uses an adaptation of binary search to identify where the first element of the smaller array must be placed in the larger array
What is galloping?
400
Algorithm is considered "intractable".
What is O(2^n) or exponential?
400
Deleted cells are not really deleted, but marked as deleted.
What is lazy deletion.
400
Tree is really stored as an array. Parents/children are found without pointers.
What is Dheap or heap stored as an array?
400
Creates a total order from a partial order of a directed graph.
What is topological ordering?
400
If a natural run is smaller than this value, insertion sort is used to increase the size.
What is minrun?
500
When run time doubles, problem size increases by a constant.
What is logarithmic time or O(log n)?
500
Probe sequence for a specific key might be: 8 11 14 17 1 4
What is double hashing?
500
Graph Algorithm that used a priority queue.
What is Dijkstra's single source shortest path?
500
A non-spanning tree edge in a graph which goes from a node to its descendant.
What is a forward edge?
500
Reason many duplicate keys causes quicksort to be inefficient.
What is partition can't divide data into equal sized pieces?