# 373 algorithms and data structures

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

## Algorithms

### Sorting Algorithms

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

- Mergesort:
- Worst-case time $O(n \log n)$
- Average-case time $O(n \log n)$
- not in-place, but stable

- Heapsort:
- Worst-case time $O(n \log n)$
- Average-case time $O(n \log n)$
- in-place, but not stable.

### Shortest Paths

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

- 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

- Kruskal’s Algorithm:
- Running time: $O(E\log E)$
- Returns list of edges in MST or a graph object containing just the spanning tree.

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

### Graph Search

[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)

[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)

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)

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.

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

AVL tree

Operation Worst-case Average-Case Insert $O(\log n)$ $O(\log n)$ Find $O(\log n)$ $O(\log n)$ Delete $O(\log n)$ $O(\log n)$ Hash Table

Operation Worst-case Average-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

ArrayList

Operation Worst-case Average-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)

Linked List

Operation Worst-case Average-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

Operation | Running time (worst- and average-case) |
---|---|

Enqueue | $O(1)$ |

Peek | $O(1)$ |

Dequeue | $O(1)$ |

- Running times are amortized for array-based implementations.

### Stack

Operation | Running time (worst- and average-case) |
---|---|

Push | $O(1)$ |

Peek | $O(1)$ |

Pop | $O(1)$ |

- Running times are amortized for array-based implementations.

### Priority Queue

Operation | Running 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)$ |