# 332 algorithms and data structures

The following algorithms and data structures from 332 can be used without any further explanation.

## Algorithms

### Sorting Algorithms

1. Quicksort:
• Worst-case time O(n^2)
• Average-case time O(n log n)
• In-place, but not stable; usually fastest in “the real world”
2. Mergesort:
• Worst-case time O(n log n)
• Average-case time O(n log n)
• not in-place, but stable
3. Heapsort:
• Worst-case time O(n log n)
• Average-case time O(n log n)
• in-place, but not stable.

### Shortest Paths

1. Dijkstra’s Algorithm:
• Running time: O(E log V + V log V)
• Precondition: All edge-weights non-negative.
• Stores distance from source to v in v.dist for every vertex v.
• Can also find path from source to v for a particular v in O(E) extra time.
2. BFS-Shortest Path:
• Running time: O(V+E)
• Precondition: All edge weights are identical (or unweighted).
• Stores distance from source to v in v.dist for every vertex v.
• Can also find path from source to v for a particular v in O(E) extra time.

### Minimum Spanning Trees

1. Kruskal’s Algorithm:
• Running time: O(E log E)
• Returns list of edges in MST or a graph object containing just the spanning tree.
2. Prim’s Algorithm:
• Running time: O(E + V log V)
• Returns list of edges in MST or a graph object containing just the spanning tree.
1. [B/D]FS modification to find connected components.

• Running Time O(V+E)
• Precondition: undirected graph.
• Stores a component number in each vertex (given two vertices, the numbers are the same if-and-only-if they are in the same component)
2. [B/D]FS modification to find weakly connected components.

• Running Time O(V+E)
• Precondition: directed graph.
• Stores a component number in each vertex (given two vertices, the numbers are the same if-and-only-if they are in the same weakly connected component)
3. DFS modification to find strongly connected components.

• Running time: O(V+E)
• Precondition: directed graph.
• Stores a SCC number in each vertex (given two vertices, the numbers are the same if-and-only if they are in the same strongly connected component)
4. DFS modification to find meta-graph (a.k.a. “condensation graph”) of G.

• Running time: O(V+E) (of the original graph
• Precondition: directed graph.
• Given vertex u of G, can get access in constant time to corresponding component vertex of condensation graph.
• Given component vertex of condensation graph, can get (in constant time) a list of the vertices of G in that component.
5. DFS modification to find topological sort.

• Running time O(V+E)
• Precondition: directed acyclic graph.
• Stores the index in the ordering in each vertex (e.g. if u is the 3rd vertex in the list, u has 3 stored inside) or returns a list of vertices in order.

## Data Structures

### Dictionaries

1. AVL tree

OperationWorst-caseAverage-Case
InsertO(log n)O(log n)
FindO(log n)O(log n)
DeleteO(log n)O(log n)
2. Hash Table

OperationWorst-caseAverage-Case
InsertO(n)O(1)
FindO(n)O(1)
DeleteO(n)O(1)
• If you can guarantee a constant number of collisions (for example, because you know the keys in advance), all worst-case times become O(1).

### Lists

1. ArrayList

OperationWorst-caseAverage-Case
Insert at frontO(n)O(n)
Insert at endO(1) (amortized)O(1)
DeleteO(n)O(n)
FindO(log n) if sorted, O(n) otherwiseO(log n) if sorted, O(n) otherwise
• In some use-cases, some of these operations can be sped up (for example, if you use lazy deletion, in a sorted array, deletion can be sped up)

OperationWorst-caseAverage-Case
Insert at frontO(1)O(1)
Insert at endO(1)O(1)
DeleteO(n)O(n)
FindO(n)O(n)

### Queue

OperationRunning time (worst- and average-case)
EnqueueO(1)
PeekO(1)
DequeueO(1)
• Running times are amortized for array-based implementations.

### Stack

OperationRunning time (worst- and average-case)
PushO(1)
PeekO(1)
PopO(1)
• Running times are amortized for array-based implementations.

### Priority Queue

OperationRunning time (worst- and average-case)
InsertO(log n)
Remove-MinO(log n)
Peek-MinO(1)
Decrease PriorityO(log n)
Build-Heap (create heap with n elements)O(n)