Algorithm Description Time Complexity

Heap
Heap Creation Complete binary tree structure O(N)
1. Initialise an array containing heap elements
2. From the last non-leaf node (parent of the last node), iterate through all parents and perform shiftDown
3. shiftDown is the process of comparing the parent to its children and determining if it needs to be shifted
down

Heap Operations Insertion O(logN)

1. Add element to end of array
2. Perform shiftUp on element until heap property is restored
ExtractMax O(logN)
1. Pop the root node (highest priority)
2. The last element in the heap is made the root
3. Perform shiftDown on the new root until heap property is restored
HeapSort O(NlogN)
1. ExtractMax until all elements are popped
BST and AVL tree
BST Operations BST height excludes root node (BST with root only has height of 0) O(h)
Insertion
1. Start from the root node Worst case: h = N
2. Traverse the BST until a suitable position is found for the new node Best case: h = logN
Deletion
1. Find node to be removed
2. Reconnect children to parent of node (if any)
Search
1. Traverse BST until node is found

AVL Tree Operations Self-balancing BST with -1 >= balanceFactor (leftTreeHeight - rightTreeHeight) <= 1
Left Rotation O(1)
1. Pick the right child of the current node to be the new root Hence BST operations
2. Current node will be left child of the new root are maintained at O(h)
3. Left child of new root will be right child of current node where h = logN
Right Rotation
1. Pick the left child of the current node to be the new root
2. Current node will be the right child of the new root
3. Right child of the new root will be right child of current node
Left-Right Rotation
 1. Pick the current node’s right child R
2. Perform left rotation on R’s left child
3. Perform right rotation on R
Right-Left Rotation
1. Pick the current node’s left child L
2. Perform right rotation on L’s right child
3. Perform left rotation on L
UFDS
Find Recursively find parent until parent[x] == x, then perform path compression by assigning parent[x] to root. O(ɑ(N))

Union Find parent of x and y, then union if parent[x] != parent[y]. Root will be representative with the higher rank. O(ɑ(N))
Graph Traversal
DFS Uses recursive stack O(V + E)
1. Mark start vertex u as visited
2. For each neighbour of u, perform DFS if not visited

BFS 1. Initialise Queue and VisitedSet O(V + E)

2. Enqueue start vertex u, visited[u] = true
3. While queue is not empty, dequeue u
4. Visit each neighbour of u and add to queue

Applications 1. Reachability test

BFS/ DFS from u, then check if v is visited
2. Counting components CC - O(k(V + E))
A subgraph of an undirected graph where any pair of vertices is connected to each other. Average case:
a. Initialise all vertices as unvisited k components, relatively
b. For each vertice, if unvisited, increment component count and perform DFS/BFS constant O(V + E) time
3. Counting Strongly Connected Components (SCC) Worst case:
SCC is a subgraph of a directed graph where every pair of vertices is reachable from each other V components
Kosaraju’s algorithm using DFS
I. Perform a DFS traversal of the graph and mark the visited vertices. Kosaraju - O(V + E)
II. After the first DFS traversal, obtain the reverse of the original graph by reversing the direction of all
edges.
III. Perform another DFS traversal on the reversed graph, starting from any unvisited vertex, but always
selecting the unvisited vertex with the highest finishing time from the first DFS traversal.
IV. Each time a DFS traversal in the reversed graph completes, it forms a strongly connected component.
Minimum Spanning Tree
Prim's Algorithm With an adjacency list, start at a vertex and form MST by picking the shortest edge until all vertices are part of the O(E + V log V) or
tree. O(E log V)
1. Start with an arbitrary vertex as the initial tree.
2. Maintain a set of vertices in the tree and a set of vertices outside the tree.
3. At each step, find the shortest edge that connects a vertex in the tree to a vertex outside the tree.
4. Add this edge to the tree and mark the newly added vertex as part of the tree.
5. Repeat until all vertices are part of the tree, resulting in a minimum spanning tree.

Kruskal's Algorithm With an edge list, pick the shortest edge until all vertices are connected. O(E log E) or O(E log V)
1. Sort the edges in ascending order of their weights.
2. Start with an empty set of edges as the initial tree.
3. Iterate through the sorted edges and add them to the tree one by one, ensuring that they do not form a cycle.
4. Use a disjoint-set data structure to keep track of connected components and detect cycles.
5. Repeat until all vertices are connected, resulting in a minimum spanning tree.
Single Source Shortest Path
Dijkstra's Algorithm 1. Start with a source vertex and initialise the distance to the source vertex as 0 and the distance to all other O((E + V)log V)
vertices as infinity.
2. Maintain a set of unvisited vertices.
3. At each step, choose the vertex with the smallest distance from the source vertex and mark it as visited.
4. Relax all edges outgoing from the chosen vertex, i.e., update the distances to its adjacent vertices if a shorter
path is found.
5. Repeat until all vertices are visited, resulting in the shortest path from the source vertex to all other vertices.

Modified Dijkstra For graphs with negative weight edges but no negative cycle. O(E log E)
1. Initialise PQ of (dist[u], u) with pair of (0, source) Same as O((E + V)log V)
2. Dequeue each pair (d, u) and check if d == D[u]. Skip relaxing if d != D[u] as d is not the min value anymore. except when E < O(V)
3. For each neighbour v of u, relax all edges
D[v] = D[v] > D[u] + edgeWeight(u, v) ? D[u] + edgeWeight(u, v) : D[v]
If v was relaxed, add to PQ

Bellman-Ford Applicable to all graphs, but slow. For each vertice, relax all edges. O(VE)
Algorithm 1. Start with a source vertex and initialise the distance to the source vertex as 0 and the distance to all other
vertices as infinity.
2. Relax all edges V-1 times, where V is the number of vertices in the graph.
3. Relaxation involves updating the distances to adjacent vertices if a shorter path is found.
4. Detect and handle negative weight cycles, which can be present in the graph
5. The shortest path is obtained after V-1 iterations.
For negative weight cycle, we perform an additional check to report.
For each edge(u, v), if D[v] < D[u] + edgeWeight(u, v) -> there is negative cycle
Topological Sort DFS based Toposort O(V + E)
1. Perform a depth-first search traversal on the graph, starting from an arbitrary vertex.
2. Mark a vertex as visited when all its adjacent vertices have been visited.
3. Add the vertex to the topological order when all its adjacent vertices are processed.
4. Reverse the topological order to obtain the correct ordering.
Kahn’s Toposort (BFS based) + better
1. Start with a vertex that has no incoming edges, i.e., in-degree of 0, as the initial step.
2. Process the vertex by adding it to the topological order.
3. Remove the vertex and its outgoing edges from the graph.
4. Update the in-degrees of the remaining vertices.
5. Repeat the above steps until all vertices are processed or a cycle is detected.

Application 1. Graph is a tree (regardless of edge weight)

DFS/ BFS as all paths are a shortest path Tree DFS/ BFS - O(V)
2. Graph is unweighted
BFS BFS - O(V+E)
3. Graph is directed and acyclic (DAG)
Toposort (DFS) then run one-pass Bellman-Ford to relax all vertices Toposort - O(V + E),
4. Graph has no negative weight edge/ cycle Bellman Ford - O(1)
Dijstra’s Algorithm -> only a few negative weight edges, otherwise Bellman-Ford
5. Graph has negative weight cycle/ all other cases
Bellman-Ford Algorithm