MODULES / M2

Advanced Data Structures & Graph Algorithms

M2 ORDER: 2

Algorithm Analysis & Design (CST306) - Module 2 Study Guide

Graph Traversals (BFS / DFS)

[SURE SHOT | ↻ REPEATED PYQ]

Section A: What is this? (The Concept)

Imagine you are exploring a massive, ancient underground tomb with many interconnected chambers. You have two ways to explore: either you visit all the rooms closest to the entrance first before going deeper, or you pick a dark corridor and keep following it as deep as it goes until you hit a dead end, then backtrack to the last intersection and try another way.

The Analogy: Breadth-First Search (BFS) is like exploring the tomb “layer by level” (visiting all neighbors first). Depth-First Search (DFS) is like a “deep dive” into the tomb (following a path until you can’t go any further).

In computer science, these are the fundamental ways we visit every node in a graph. BFS uses a Queue (First-In-First-Out) to keep track of neighbors, while DFS uses recursion or a Stack (Last-In-First-Out) to dive deep.

Section C: Step-by-Step Worked Example (The Application)

Example: DFS Traversal & Edge Classification (University Question) Consider a Directed Graph with edges: (1,2),(2,4),(4,6),(1,3),(3,5),(5,7),(5,8),(1,8),(6,2),(5,4)(1,2), (2,4), (4,6), (1,3), (3,5), (5,7), (5,8), (1,8), (6,2), (5,4). Perform DFS starting at node 1 (pick neighbors in numerical order).

  1. DFS Sequence: 1→2→4→61 \to 2 \to 4 \to 6.
    • From 6, neighbor 2 is already visited. Backtrack to 1.
    • From 1, visit 3 →5→7\to 5 \to 7.
    • From 7, no neighbors. Backtrack to 5.
    • From 5, visit 8.
  2. Edge Classification:
    • Tree Edges: (1,2), (2,4), (4,6), (1,3), (3,5), (5,7), (5,8). (Edges forming the DFS tree).
    • Backward Edge: (6,2). (Connects descendant 6 to ancestor 2). Indicates a cycle.
    • Forward Edge: (1,8). (Connects ancestor 1 to descendant 8, not via tree path).
    • Cross Edge: (5,4). (Connects 5 and 4 which have no ancestor/descendant relationship in this DFS tree).

Section D: How to Write This in the Exam (The Strategy)

  • Start With: The formal algorithm for BFS/DFS. Mention the data structure used (Queue for BFS, Stack/Recursion for DFS).
  • Body: For traversal questions, always show the state of the Queue (for BFS) or the Recursion Stack/Discovery times (for DFS) at each step. If asked for edge classification, label the edges on the graph diagram.
  • Traps: If the question says “pick neighbors in alphabetical order,” strictly follow it. Missing a single node in a complex graph will lose symmetry and marks.
  • Close With: State the applications (e.g., BFS for shortest path in unweighted graphs, DFS for cycle detection or Topological Sort).

AVL Trees Construction

[SURE SHOT | ↻ REPEATED PYQ]

Section A: What is this? (The Concept)

Imagine you are building a library shelf. If you keep adding books only to the right side, the shelf will eventually tip over. To keep it stable, you need to rearrange the books so the weight is evenly distributed.

The Analogy: An AVL Tree is a “self-balancing” library shelf. In a normal Binary Search Tree, if you insert numbers in order (1, 2, 3, 4…), the tree becomes a straight line (unbalanced), making it slow to search. An AVL tree detects whenever one side gets too “heavy” and performs a “rotation” (rearranging) to keep the height small.

The “weight” here is called the Balance Factor. An AVL tree ensures that for every single node, the height difference between its left and right sides is never more than 1.

Section B: Exam-Ready Theory (The Rigor)

1. Definition: An AVL tree is a height-balanced Binary Search Tree (BST). 2. Balance Factor (BF): BF(node)=Height(Left Subtree)−Height(Right Subtree)BF(\text{node}) = \text{Height}(\text{Left Subtree}) - \text{Height}(\text{Right Subtree}) A node is considered balanced if its BF is {−1,0,+1}\{-1, 0, +1\}. If BF becomes +2+2 or −2-2, the tree is unbalanced.

3. The 4 AVL Rotations:

  • LL Rotation (Single Right): Needed when a node is inserted into the left subtree of the left child.
  • RR Rotation (Single Left): Needed when a node is inserted into the right subtree of the right child.
  • LR Rotation (Double): Left rotation followed by Right rotation. Needed when inserted into the right subtree of the left child.
  • RL Rotation (Double): Right rotation followed by Left rotation. Needed when inserted into the left subtree of the right child.

4. Complexity: All operations (Search, Insertion, Deletion) take O(log⁡n)O(\log n) time because the height is always kept logarithmic.

Section C: Step-by-Step Worked Example (The Application)

Example: Construct AVL tree (April 2025 University Question) Insert nodes: 50, 20, 60, 10, 8, 15, 32, 46, 11, 48

  1. Insert 50, 20, 60:
    • Root(50), Left(20), Right(60). All BFs within {−1,0,1}\{-1, 0, 1\}.
  2. Insert 10: Goes to Left of 20.
  3. Insert 8: Goes to Left of 10.
    • Imbalance at 20: BF(20) = 2. Path: Left-Left (LL).
    • Action: Single Right Rotation at 20.
    • Result: 10 becomes parent of 8 and 20.
  4. Insert 15: Goes to Right of 10, Left of 20.
    • Imbalance at 50: BF(50) = 2. Path: Left-Right (LR).
    • Action: Double Rotation (LR) at 50.
    • Result: 15 becomes the new root (or sub-root depending on depth).
  5. Continue for 32, 46, 11, 48:
    • Note: For the exam, you must draw the state after every single rotation.
    • Key State (Final): The tree remains balanced with height 3.

Section D: How to Write This in the Exam (The Strategy)

  • Start With: Define AVL tree and the Balance Factor formula.
  • Body: When asked to construct a tree, draw the tree after every single insertion. Calculate and write the BF for every node after each step.
  • Traps: If you find an imbalance, identify the type of rotation (LL, RR, LR, RL) before drawing the rotated version. Do not skip steps; the examiner gives marks for the intermediate unbalanced states and the rotation labels.
  • Close With: Verify that the final tree satisfies the BST property (Left < Root < Right) and all BFs are within {−1,0,1}\{-1, 0, 1\}.

Disjoint Sets & Strongly Connected Components

[HIGH PROB | ↻ REPEATED PYQ]

Section A: What is this? (The Concept)

Disjoint Sets: Imagine a group of people at a party. Initially, everyone is a stranger (their own set). As people talk, they form “friend groups.” If person A knows B, and B knows C, then A, B, and C are in the same group.

The Analogy: Disjoint Sets (Union-Find) help us track these groups. “Find” asks “Who is the leader of your group?” and “Union” says “Merge these two groups together under one leader.”

Strongly Connected Components (SCC): In a directed map of one-way streets, an SCC is a neighborhood where you can drive from any house to any other house and still be able to get back.

The Analogy: If you can go from A to B, but never from B back to A, they are NOT in the same SCC. SCCs are “circular” clusters in a directed graph.

Section B: Exam-Ready Theory (The Rigor)

1. Disjoint Set Operations

  • Make-Set(x): Creates a new set containing only element xx.
  • Find(x): Returns the representative (root) of the set containing xx.
  • Union(x, y): Merges the sets containing xx and yy.
  • Optimizations (The Heuristics):
    • Union by Rank: Always attach the smaller tree under the root of the larger tree to keep depth small.
    • Path Compression: During “Find”, make every node on the path point directly to the root to flatten the tree.

2. Strongly Connected Components (Kosaraju’s Algorithm)

  • A 2-Pass algorithm using DFS.
  • Steps:
    1. Perform DFS on original graph GG and push nodes onto a Stack based on their finishing times.
    2. Reverse all edges of the graph to get GTG^T (Transpose Graph).
    3. Pop nodes from the Stack. If the node is unvisited, perform DFS on GTG^T starting from it. Each such DFS visit identifies one SCC.
  • Complexity: O(V+E)O(V + E).

Section C: Step-by-Step Worked Example (The Application)

Example 1: Union by Rank and Path Compression Trace (University Question) Suppose we have sets {1},{2},{3},{4},{5},{6}\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}. Perform: Union(1,2),Union(3,4),Union(5,6),Union(1,3)Union(1,2), Union(3,4), Union(5,6), Union(1,3).

  1. Union(1,2): Rank(1)=0, Rank(2)=0. Attach 2 to 1. Root=1, Rank(1)=1.
  2. Union(3,4): Rank(3)=0, Rank(4)=0. Attach 4 to 3. Root=3, Rank(3)=1.
  3. Union(5,6): Rank(5)=0, Rank(6)=0. Attach 6 to 5. Root=5, Rank(5)=1.
  4. Union(1,3): Both roots have Rank 1. Attach 3 to 1. Root=1, Rank(1)=2.
  5. Find(4) with Path Compression:
    • Path: 4→3→14 \to 3 \to 1.
    • Compression: Node 4 is reattached directly to Root 1.
    • Result: Future Find(4) takes O(1)O(1) time.

Example 2: Kosaraju’s SCC Trace (University Question) Graph: 1→4,4→7,7→1,9→7,9→3,6→9,3→6,8→6,8→2,2→5,5→81 \to 4, 4 \to 7, 7 \to 1, 9 \to 7, 9 \to 3, 6 \to 9, 3 \to 6, 8 \to 6, 8 \to 2, 2 \to 5, 5 \to 8.

  1. Pass 1 (DFS Finish Stack): [2,5,8,3,6,9,1,4,7][2, 5, 8, 3, 6, 9, 1, 4, 7] (Top is 8).
  2. Pass 2 (DFS on Reversed Graph):
    • Pop 8: Visits {8,5,2}\{8, 5, 2\}. SCC 1 = {2, 5, 8}.
    • Pop 9: Visits {9,6,3}\{9, 6, 3\}. SCC 2 = {3, 6, 9}.
    • Pop 1: Visits {1,7,4}\{1, 7, 4\}. SCC 3 = {1, 4, 7}.

Section D: How to Write This in the Exam (The Strategy)

  • Start With: For Disjoint sets, define the three operations. For SCC, define what “Strongly Connected” means.
  • Body: For Kosaraju’s, draw the Original Graph, the Stack state, the Reversed Graph, and finally list the sets of nodes in each SCC.
  • Traps: In Disjoint Sets, remember that Union(a, b) actually performs Union(Find(a), Find(b)). You merge the roots, not the leaf nodes.
  • Close With: Mention the time complexity O(V+E)O(V+E) for both SCC and optimized Disjoint Set operations.

Topological Sort

[PART A FOCUS | HIGH FREQ]

Section A: What is this? (The Concept)

Imagine you are getting dressed. You can’t put on your shoes before your socks, and you can’t put on your jacket before your shirt. Some tasks depend on others.

The Analogy: Topological Sort is the “Getting Dressed” sequence. It takes a list of tasks with dependencies (a Directed Acyclic Graph) and puts them in a valid linear order so that no task is started before its requirements are met.

Section B: Exam-Ready Theory (The Rigor)

  • Definition: A linear ordering of vertices such that for every directed edge (u,v)(u, v), vertex uu comes before vv in the ordering.
  • Constraint: Only possible for Directed Acyclic Graphs (DAGs). If there is a cycle, no topological sort exists.
  • Kahn’s Algorithm (In-degree method):
    1. Find all nodes with In-degree = 0 (no incoming edges).
    2. Add them to a Queue.
    3. While Queue is not empty: a. Pop node uu, add to result. b. For each neighbor vv of uu, decrement In-degree of vv. c. If In-degree of vv becomes 0, add to Queue.
  • Complexity: O(V+E)O(V + E).

Section C: Step-by-Step Worked Example (The Application)

Example: Perform Topological Sort on a DAG Consider a DAG with vertices {1, 2, 3, 4, 5, 6} and edges: (1, 2), (1, 3), (2, 4), (3, 4), (4, 5), (4, 6).

  1. Calculate In-degrees:
    • Node 1: 0
    • Node 2: 1 (from 1)
    • Node 3: 1 (from 1)
    • Node 4: 2 (from 2, 3)
    • Node 5: 1 (from 4)
    • Node 6: 1 (from 4)
  2. Step 1: Queue = [1]. Result = [].
    • Pop 1. Neighbors: 2, 3.
    • In-degree(2) = 0, In-degree(3) = 0.
    • Queue = [2, 3]. Result = [1].
  3. Step 2: Pop 2. Neighbor: 4.
    • In-degree(4) = 1.
    • Queue = [3]. Result = [1, 2].
  4. Step 3: Pop 3. Neighbor: 4.
    • In-degree(4) = 0.
    • Queue = [4]. Result = [1, 2, 3].
  5. Step 4: Pop 4. Neighbors: 5, 6.
    • In-degree(5) = 0, In-degree(6) = 0.
    • Queue = [5, 6]. Result = [1, 2, 3, 4].
  6. Step 5: Pop 5. No neighbors.
    • Queue = [6]. Result = [1, 2, 3, 4, 5].
  7. Step 6: Pop 6. No neighbors.
    • Queue = []. Result = [1, 2, 3, 4, 5, 6].

Final Topological Ordering: [1, 2, 3, 4, 5, 6] (or [1, 3, 2, 4, 6, 5] etc.)

Section D: How to Write This in the Exam (The Strategy)

  • Start With: Define DAG and the condition for Topological Sort.
  • Body: List the In-degree of every node in a table. Show how the In-degrees change as you “remove” nodes.
  • Traps: If you are asked to find “any two” topological orderings, show how picking a different node from the “In-degree 0” set changes the final sequence.
  • Close With: State applications like task scheduling or instruction sequencing in compilers.