Graph Theory, Hashing, and Priority Queues

Flashcards covering algorithm complexities for Prim's and Kruskal's, Disjoint Set operations, graph connectivity terminology, search algorithms (BFS/DFS), hashing techniques, and Priority Queue data structure performance.

Prim's Algorithm (Adjacency List + Binary Heap) Complexity

The total time complexity is $O((V + E) \text{ } \text{log} \text{ } V)$, where binary heap operations are $O(V \text{ } \text{log} \text{ } V)$ and $O(E \text{ } \text{log} \text{ } V)$, and initialization is $O(V)$.

Prim's Algorithm (Adjacency List + Unsorted) Complexity

The total time complexity is $O(V^2)$, with operations broken into $O(V)$ for initialization, $O(V \times V)$ for extract-min, and $O(E \times 1)$ for decrease-key.

Prim's Algorithm (Adjacency Matrix + Binary Heap) Complexity

The total time complexity is $O(V^2 \text{ } \text{log} \text{ } V)$, based on $O(V)$ initialization and $O(V \text{ } \text{log} \text{ } V)$ heap operations.

Prim's Algorithm (Adjacency Matrix + Sorted) Complexity

The total time complexity is $O(V^3)$ due to $O(V^2 + V)$ operations.

Kruskal's Algorithm Initialization

The complexity of the making/initialization step is $O(V)$.

Kruskal's Algorithm Sorting

The complexity of sorting the edges is $O(E \text{ } \text{log} \text{ } E)$.

Total Kruskal's Complexity

The total complexity is $O((E + V) \text{ } \text{log} \text{ } V)$ or $E \text{ } \text{log} \text{ } E + E \text{ } \text{log} \text{ } V$.

MakeSet(x)

A Disjoint Set operation with a complexity of $O(1)$.

Union

A Disjoint Set operation that combines sets with a complexity of $O(1)$.

FindSet

A Disjoint Set operation that finds and returns a pointer to $x$ (which is $y$) with a complexity of $O(\text{min}(x, \text{min } y))$.

Strongly Connected Graph

A graph where you can reach all other nodes through a directed edge or path.

Weakly Connected Graph

A graph that would be strongly connected if the edges were undirected; a component can be its own SCC (Strongly Connected Component).

Sink

A node with an outdegree of $0$.

Source

A node with an indegree of $0$.

BFS (Breadth First Search)

Used for unweighted, cyclic, directed or undirected graphs with a complexity of $O(V + E)$.

DFS Discovery Labels

Labels used during Depth First Search including undiscovered, discovery, forward, backward, and cross.

Topological Sort

A method to order a graph into a list; it will terminate early if there is a cycle and only works with a DAG (Directed Acyclic Graph).

Kahn's Algorithm

A method for Topological Sort that uses a queue and indegree counts.

Unordered Map

A data structure using hashing with $O(1)$ average complexity for find, insert, and erase; it is less memory efficient but faster than other maps.

Chaining

A collision method for hashing where the key is mapped via $\text{key} \text{ } \% \text{ } \text{table size}$; remains $O(1)$ if the hash function is good.

Linear Probing

A collision resolution method that finds the next available spot and can loop around; uses the formula $h(x) = h_1(x) + i$ where $i = 0, 1, 2, \text{ } ...$

Quadratic Probing

A collision resolution method using the hash function formula $f(x, i) = (h(x) + i^2) \text{ } \% \text{ } 5$, where $i$ increases upon collision.

Double Hashing

A complexity resolution method where $h_1(x) = x - 3$ and $h_2(x) = x \times 7$ are used in the formula $f(x, i) = (h_1(x) + i \times h_2(x)) \text{ } \% \text{ } 5$.

Priority Queue (ADT) Operations

Standard operations for this Abstract Data Type include top, push, and pop.

Heapify Complexity

The time complexity for the heapify operation is $O(n)$.

Heapify Swaps

The number of swaps in heapify is calculated as $\text{node number} \times \text{height}$, not the depth.

Sorted Array Complexity (Priority Queue)

For a sorted array, push is $O(n)$, pop is $O(1)$, and top is $O(1)$.

Unsorted Array Complexity (Priority Queue)

For an unsorted array, push is $O(1)$, pop is $O(n)$, and top is $O(n)$.

Heap Complexity (Priority Queue)

For a heap, push is $O(\text{log } n)$, pop is $O(\text{log } n)$, and top is $O(1)$.