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.

Graph Search

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

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

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

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

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

• Running times are amortized for array-based implementations.

Stack

• Running times are amortized for array-based implementations.

Priority Queue