Graphs, hashing and sorting techniques notes — Unit 5

A Graph is a non-linear data structure consisting of a finite set of Vertices (or Nodes) and a set of Edges that connect them. Mathematically, $G = (V, E)$.

Unlike trees, graphs have no root node, and they can contain cycles (loops). In fact, a Tree is simply a special type of graph: a connected acyclic graph.

⇒1.1 Types of Graphs

• Directed Graph (Digraph): Edges have a direction (represented by arrows). Relationship is one-way.
• Undirected Graph: Edges have no direction. Relationship is mutual.
• Weighted Graph: Edges have a numerical weight (cost, distance) attached to them.
• Cyclic vs Acyclic: A graph containing at least one cycle is cyclic.

Graphs are typically represented in code in two ways, depending on whether the graph is dense (many edges) or sparse (few edges).

⇒2.1 Adjacency Matrix

A 2D array of size $V \times V$ where $V$ is the number of vertices. If there is an edge from vertex $i$ to vertex $j$, then `matrix[i][j] = 1` (or weight), otherwise `0`.

• Pros: $O(1)$ time to check if an edge exists between two vertices.
• Cons: Space complexity is $O(V^2)$, which wastes massive memory for sparse graphs.

⇒2.2 Adjacency List

An array of Linked Lists. The size of the array is equal to the number of vertices. `array[i]` points to a linked list containing all vertices adjacent to vertex $i$.

• Pros: Space complexity is $O(V + E)$, highly efficient for sparse graphs.
• Cons: $O(V)$ worst-case time to check if a specific edge exists.

Traversing a graph involves visiting every vertex. Because graphs can have cycles, we must maintain a `visited` array (or hash set) to avoid infinite loops.

⇒3.1 Breadth-First Search (BFS)

Explores the graph layer by layer, visiting all immediate neighbours before moving deeper. Uses a Queue.

• Pick a starting vertex, mark it visited, enqueue it.
• While queue is not empty, dequeue a vertex.
• For every unvisited adjacent vertex, mark it visited and enqueue it.

Use case: Finding the shortest path on unweighted graphs.

⇒3.2 Depth-First Search (DFS)

Explores as deep as possible along each branch before backtracking. Uses a Stack (usually via Recursion).

• Visit a vertex and mark it visited.
• Recursively call DFS for all its unvisited adjacent vertices.

Use case: Topological sorting, cycle detection.

A Spanning Tree of a connected, undirected graph is a subgraph that is a tree (no cycles) and includes all the vertices of the original graph.

A Minimum Spanning Tree (MST) is a spanning tree whose sum of edge weights is as small as possible. (Crucial for network routing and laying cables).

⇒4.1 Prim's Algorithm

A greedy algorithm that builds the MST vertex by vertex.

• Start with an empty MST and pick an arbitrary starting vertex.
• Maintain a set of vertices already included in the MST.
• At each step, find the edge with the minimum weight that connects a vertex in the MST set to a vertex outside the MST set.
• Add that edge and vertex to the MST.
• Repeat until all vertices are included.

Another greedy algorithm for finding the MST, but this one builds it edge by edge.

⇒5.1 The Algorithm

• Sort all the edges in the graph in ascending order of their weights.
• Pick the smallest edge. Check if adding it to the MST forms a cycle.
• If a cycle is NOT formed, include the edge in the MST.
• If a cycle IS formed, discard the edge.
• Repeat until there are $(V - 1)$ edges in the MST.

⇒5.2 Disjoint Set (Union-Find)

To efficiently check if adding an edge forms a cycle, Kruskal's algorithm uses a data structure called Disjoint Set Union (DSU). If the two endpoints of an edge belong to the same set, adding the edge will form a cycle.

Hashing is a technique used to uniquely identify a specific object from a group of similar objects. It is used to achieve $O(1)$ average time complexity for Search, Insert, and Delete operations.

⇒6.1 Key Components

• Key: The unique identifier (e.g., student ID, string).
• Hash Function: A mathematical function that converts a large Key into a small integer (index).
• Hash Table: An array where the data is actually stored. The index computed by the Hash Function is used to store/retrieve data in this array.

Example: A hash function $H(x) = x \pmod{10}$. The key `54` maps to index `4`. We store the data at `HashTable[4]`.

⇒6.2 The Collision Problem

Since the Hash Table is smaller than the universe of possible Keys, two different keys will eventually produce the same hash index. E.g., `54` and `24` both map to index `4`. This is called a Collision.

When a collision occurs, we must resolve it. There are two primary categories of collision resolution: Chaining (Closed Addressing) and Open Addressing.

⇒7.1 Separate Chaining

In Separate Chaining, the Hash Table is an array of Linked List pointers. When a collision occurs, the new element is simply appended to the linked list at that index.

• Pros: Simple to implement. Hash table never "fills up" (lists just grow longer). Deletion is easy.
• Cons: Cache performance is poor due to linked lists. Extra memory is used for pointers.

⇒7.2 Open Addressing

In Open Addressing, all elements are stored directly inside the Hash Table array. If a collision occurs, we probe (search) the array for the next available empty slot.

⇒8.1 Linear Probing

If a collision occurs at index `i`, we check `i+1`, `i+2`, etc., wrapping around to the beginning if necessary, until an empty slot is found.

⇒8.2 Quadratic Probing

To avoid primary clustering, we probe at intervals of squares: $1^2, 2^2, 3^2$. We check `i+1`, `i+4`, `i+9`.

⇒8.3 Double Hashing

Uses a second hash function $Hash_2(x)$ to determine the step size for probing. This resolves both primary and secondary clustering.

Sorting is arranging data in a specific order (ascending or descending).

⇒9.1 Bubble Sort

Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The largest element 'bubbles' to the end in the first pass.

• Time Complexity: Worst $O(n^2)$, Best $O(n)$ (if optimized with a flag).
• Space Complexity: $O(1)$

⇒9.2 Selection Sort

Divides the array into a sorted and unsorted part. Repeatedly finds the minimum element from the unsorted part and puts it at the beginning.

• Time Complexity: $O(n^2)$ in all cases.
• Space Complexity: $O(1)$
• Note: Makes the minimum possible number of swaps ($O(n)$ swaps).

⇒10.1 Insertion Sort

Builds the final sorted array one item at a time. Takes an element and inserts it into its correct position in the already sorted part (like sorting playing cards in your hand).

• Time Complexity: Worst $O(n^2)$, Best $O(n)$ (when already sorted).
• Advantage: Highly efficient for small arrays or nearly sorted arrays.

⇒10.2 Merge Sort (Divide & Conquer)

Recursively divides the array into two halves until arrays of size 1 are reached. Then, it merges the smaller sorted arrays to produce a larger sorted array.

• Time Complexity: $O(n \log n)$ in all cases (Best, Avg, Worst).
• Space Complexity: $O(n)$ auxiliary space required for the temporary merge array.
• Advantage: Guaranteed $O(n \log n)$ performance. Highly parallelizable.

Another Divide & Conquer algorithm. It picks an element as a pivot and partitions the given array around the picked pivot, placing smaller elements to the left and larger elements to the right.

⇒11.1 Algorithm

• Choose a pivot (usually last element, first element, or median).
• Partitioning: Rearrange array so pivot is in its final sorted position.
• Recursively apply Quick Sort to the left sub-array.
• Recursively apply Quick Sort to the right sub-array.

⇒11.2 Complexity

• Best/Avg Time Complexity: $O(n \log n)$.
• Worst Time Complexity: $O(n^2)$. This happens when the array is already sorted (or reverse sorted) and the pivot chosen is always the greatest/smallest element.
• Space Complexity: $O(\log n)$ stack space (in-place sorting).

Despite the $O(n^2)$ worst case, Quick Sort is often faster in practice than Merge Sort because its inner loop can be efficiently implemented on most architectures, and it doesn't require $O(n)$ extra memory.

⇒12.1 Heap Sort

Uses the Max-Heap data structure.

• Build a Max-Heap from the unsorted array.
• The largest item is stored at the root of the heap.
• Swap it with the last item of the heap followed by reducing the size of heap by 1.
• Heapify the root of the tree.
• Repeat until size of heap is greater than 1.

Time Complexity: $O(n \log n)$ in all cases.
Space Complexity: $O(1)$ (in-place).

⇒12.2 Radix Sort (Non-Comparison Sort)

Sorts numbers digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD). Uses Counting Sort as a stable subroutine.

Time Complexity: $O(d \cdot (n + b))$ where $d$ is number of digits, $b$ is the base (e.g., 10).

A sorting algorithm is said to be Stable if two objects with equal keys appear in the same order in the sorted output as they appear in the unsorted input.

⇒13.1 Why does Stability matter?

Consider sorting a list of students first by Name, and then sorting by Grade. If the Grade sort is stable, students with the same grade will remain sorted alphabetically by Name. If it is unstable, the alphabetical order is destroyed.

⇒13.2 Stable vs Unstable Algorithms

This concludes the final unit of Data Structures and Algorithms.

⇒14.1 University Exam Checklist

• Represent a given graph using an Adjacency Matrix and Adjacency List.
• Write the algorithm for Breadth-First Search (BFS) and Depth-First Search (DFS).
• Trace Prim's and Kruskal's algorithms to find the MST of a given weighted graph.
• Explain collision resolution using Separate Chaining and Linear Probing.
• Compare the time and space complexities of Merge Sort and Quick Sort.

⇒14.2 Placement Interview Focus

• Detect a cycle in a Directed Graph (using DFS and recursion stack).
• Topological Sorting of a Directed Acyclic Graph (DAG).
• Explain how a HashMap handles collisions internally (e.g., Java's HashMap switching to Trees).
• Why is Quick Sort preferred over Merge Sort for arrays, but Merge Sort preferred for Linked Lists?
• Given an array of 0s, 1s, and 2s, sort it in $O(n)$ time and $O(1)$ space (Dutch National Flag problem).