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.

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

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)