# Shared Flashcard Set

## Details

GT CS1332 Test 2 Fall 2012
Review for the third test in GT's CS1332 from Fall 2012
22
Computer Science
Undergraduate 2
11/27/2012

## Cards Return to Set Details

Term
 bubble sort big o
Definition
 Best nAvg n squaredWorst n squared
Term
 insertion sort big o
Definition
 Best nAvg n squaredWorst n squared
Term
 selection sort big o
Definition
 all n squared
Term
 merge sort big o
Definition
 all n log n
Term
 quick sort big o
Definition
 Best n log nAvg n log nWorst n squared
Term
 radix sort big o
Definition
 all kn
Term
 stable sort examples
Definition
 bubble, insertion, merge, radix
Term
 online sort examples
Definition
 insertion
Term
 in-place sort examples
Definition
 bubble, insertion, selection, quick
Term
 what is a stable sort?
Definition
 one that maintains the order (from unsorted to sorted) of entries with the same key
Term
 what is an in-place sort?
Definition
 one that uses a constant and limited amount of memory when executed
Term
 what is an online sort?
Definition
 one that sorts as it is given each entry as opposed to those that are given all entries at once
Term
 vertex
Definition
 node in a graph
Term
 edge
Definition
 a connection between two nodes
Term
 BFS
Definition
 shortest path unweighted graph (breadth-first search)
Term
 DFS
Definition
 connectivity - just find a path between 2 vertices (depth-first search)
Term
 Dijkstra
Definition
 shortest path between two vertices in a weighted graph
Term
 Kruskal's
Definition
 uses disjoint set data structure. looks at all edges simultaneusly andadds the least weight edge that doesn't create a cycle.
Term
 Running times of operations on a Disjoint Set
Definition
 O(log n)
Term
 KMP big o
Definition
 m+n
Term
 boyer-moore big o
Definition
 mnbut can be improved to m+n
Term
 rabin karp big o
Definition
 mnbut m+n with a well behaving hash function
Supporting users have an ad free experience!