# 373 algorithms and data structures

The following algorithms and data structures from 373 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
Insert\$O(\log n)\$\$O(\log n)\$
Find\$O(\log n)\$\$O(\log n)\$
Delete\$O(\log n)\$\$O(\log n)\$
2. Hash Table

OperationWorst-caseAverage-Case
Insert\$O(n)\$\$O(1)\$
Find\$O(n)\$\$O(1)\$
Delete\$O(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 front\$O(n)\$\$O(n)\$
Insert at end\$O(1)\$ (amortized)\$O(1)\$
Delete\$O(n)\$\$O(n)\$
Find\$O(\log n)\$ if sorted, \$O(n)\$ otherwise\$O(\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 front\$O(1)\$\$O(1)\$
Insert at end\$O(1)\$\$O(1)\$
Delete\$O(n)\$\$O(n)\$
Find\$O(n)\$\$O(n)\$

### Queue

OperationRunning time (worst- and average-case)
Enqueue\$O(1)\$
Peek\$O(1)\$
Dequeue\$O(1)\$
• Running times are amortized for array-based implementations.

### Stack

OperationRunning time (worst- and average-case)
Push\$O(1)\$
Peek\$O(1)\$
Pop\$O(1)\$
• Running times are amortized for array-based implementations.

### Priority Queue

OperationRunning time (worst- and average-case)
Insert\$O(\log n)\$
Remove-Min\$O(\log n)\$
Peek-Min\$O(1)\$
Decrease Priority\$O(\log n)\$
Build-Heap (create heap with n elements)\$O(n)\$