CS301 — Final Term Summary (Lectures 23–45)

📘 Lecture 23 — Data Structures Lecture No. 23

📖 Overview: This lecture continues the discussion of AVL tree rotations by presenting the actual C++ code for single and double rotations. It covers single right rotation, single left rotation, double right-left rotation, and double left-right rotation in detail, then introduces deletion in AVL trees and the five cases that determine which rotation to apply. Understanding these rotations is essential for maintaining balanced trees during both insertion and deletion operations.

🗂️ Topics Covered

The lecture covers the code implementation of single right rotation and single left rotation, including the height function used to reassign heights after rotation. It then presents double right-left rotation and double left-right rotation as combinations of single rotations. The second half introduces deletion in AVL trees, explaining that unlike insertion which requires at most one rotation, deletion may require O(log N) rotations. Finally, it details the five cases of deletion (1a, 1b, 2a, etc.) that determine what action to take at each level.

📝 Lecture Summary

Single Right Rotation

The SingleRightRotation function takes a TreeNode pointer named k2 as its argument. If k2 is NULL, the function returns NULL. Otherwise, the rotation process begins by identifying k1 as the left child of k2 — k1 will become the new root after rotation. The tree Y (the right subtree of k1) moves to become the left subtree of k2. Then k2 becomes the right child of k1. After these pointer changes, the inorder traversal (X k1 Y k2 Z) remains unchanged from before the rotation.

🔑 Definition — Single Right Rotation: A rotation applied when a node's left subtree is two levels deeper than its right subtree, performed by making the left child the new root and moving the original root down to the right.

📐 Formula: New root = k2→getLeft(); k2→setLeft(k1→getRight()); k1→setRight(k2)

📌 Example: Given a tree where k2 is the root with balance factor 2 (left subtree height = 3, right subtree height = 1), single right rotation promotes k1 (the left child) to root, moves Y (k1's right subtree) to k2's left, and makes k2 the right child of k1. After rotation, heights are reassigned: the height of k2 is set to Max(height(k2→getLeft()), height(k2→getRight())) + 1, and similarly for k1.

Height Function

The height function is a utility used by rotation routines. It takes a TreeNode pointer as an argument. If the node is not NULL, it returns the node's getHeight() value. If the node is NULL (empty tree), by definition the height is -1.

🔑 Definition — Height Function: A helper function that returns the stored height of a node, or -1 if the node pointer is NULL.

📐 Formula: height(node) = node→getHeight() if node != NULL, otherwise -1

Single Left Rotation

The SingleLeftRotation function takes a TreeNode pointer named k1 as its argument. This is symmetrical to single right rotation. Here, k2 (the right child of k1) will become the new root. The tree Y (the left subtree of k2) becomes the right subtree of k1. Then k1 is set as the left child of k2. Heights are reassigned first for k1 (the demoted node), then for k2 (the new root). Finally, k2 is returned as the new root of the tree.

🔑 Definition — Single Left Rotation: A rotation applied when a node's right subtree is two levels deeper than its left subtree, performed by making the right child the new root and moving the original root down to the left.

📐 Formula: k2 = k1→getRight(); k1→setRight(k2→getLeft()); k2→setLeft(k1)

🔑 Definition — Inorder Traversal Preservation: A property of all AVL rotations that the inorder sequence of nodes remains the same before and after rotation, ensuring the BST ordering property is maintained.

Double Right-Left Rotation

The doubleRightLeftRotation function takes k1 as its argument. This rotation combines two single rotations applied in sequence. First, a single right rotation is performed on k3 (k1's right child). The call singleRightRotation(k1->getRight()) passes k3 to the single right rotation function, which finds k3's left child k2 and promotes k2 upward while moving k3 downward. The tree C (k2's left subtree) becomes the right subtree of k3. After this first step, a single left rotation is performed with k1 as the root. This second rotation promotes k2 (now the right child of k1) to become the new root while k1 moves down as the left child of k2.

🔑 Definition — Double Right-Left Rotation: A two-step rotation (first right, then left) used when the right child of the unbalanced node has a left child that is the cause of the imbalance.

📐 Formula: k1→setRight(singleRightRotation(k1→getRight())); return singleLeftRotation(k1)

💡 Why this matters: Double rotations handle the "zig-zag" case where a single rotation alone would not restore balance. They are implemented by reusing the single rotation routines, demonstrating good code reuse.

Double Left-Right Rotation

The doubleLeftRightRotation function takes k3 as its argument. This is the mirror image of double right-left rotation. First, a single left rotation is performed on k1 (k3's left child). The call singleLeftRotation(k3->getLeft()) passes k1 to the single left rotation function, which promotes k2 (k1's right child) upward while k1 moves down as the left child of k2. The tree B (k2's left subtree) becomes the right subtree of k1. After this first step, a single right rotation is performed with k3 as the root. This second rotation promotes k2 (now the left child of k3) to become the new root while k3 moves down as the right child of k2. The tree C (k2's right subtree) becomes the left subtree of k3.

🔑 Definition — Double Left-Right Rotation: A two-step rotation (first left, then right) used when the left child of the unbalanced node has a right child that is the cause of the imbalance.

📐 Formula: k3→setLeft(singleLeftRotation(k3→getLeft())); return singleRightRotation(k3)

🔑 Definition — Property of AVL Insertion: When inserting a node in an AVL tree, at most one single rotation or one double rotation is needed to rebalance the tree.

Deletion in AVL Tree

Deletion in AVL trees is considerably more complex than insertion. While insertion requires at most one rotation, deletion may require O(log₂ N) rotations in the worst case — one at each level from the deleted node up to the root. The deletion process first removes the node as in a standard Binary Search Tree (BST), following the same three cases: (I) deleting a leaf node, (II) deleting a node with one child, and (III) deleting a node with two children. After deletion, we traverse upward from the deleted node checking the balance of each node at each level up to the root, performing rotations whenever the AVL condition is violated.

🔑 Definition — Deletion in AVL Tree: The process of removing a node from an AVL tree while maintaining the height-balanced property through rotations, potentially requiring multiple rotations at different levels.

🔑 Definition — Worst Case of Deletion: A scenario where deleting a single node causes imbalance at every level of the tree, requiring log₂ N rotations to restore balance.

📌 Example: Consider a tree where all non-leaf nodes in the left subtree have balance -1 (right subtree deeper than left). Deleting node A (a leaf in the far left) causes node C's balance to become 2 (left subtree height 0, right subtree height 2). After a single left rotation on the C-D link, node F's balance becomes -2, requiring another left rotation on the F-I link. This pattern continues up to the root N, demonstrating that rotations may be needed at every level.

Cases of Deletion in AVL Tree

There are five cases to consider when deleting from an AVL tree, which determine what action (rotation or simple balance change) is needed.

Case 1a: The parent of the deleted node had a balance of 0 and the node was deleted in the parent's left subtree. Action: Change the balance of the parent node and stop. No further effect on higher nodes. No rotation needed.

📌 Example: In a perfectly balanced tree with root 4, deleting node 1 (left child of node 2) changes node 2's balance from 0 to -1. Node 4's balance remains 0, so no further action is needed.

Case 1b: The parent of the deleted node had a balance of 0 and the node was deleted in the parent's right subtree. Action: Change the balance of the parent node and stop. No further effect on higher nodes. This is symmetric to Case 1a.

Case 2a: The parent of the deleted node had a balance of 1 and the node was deleted in the parent's left subtree. Action: Change the balance of the parent node to 0. However, this deletion may have caused imbalance in higher nodes, so continue checking up to the root and perform rotations where necessary.

🔑 Definition — Balance Notation: The symbol inside a node indicates the balance condition: a horizontal line (—) means balance 0 (equal heights), a downward-right symbol means left subtree is shorter (balance negative), and other symbols indicate other balance conditions.

⭐ Key Takeaways

Single rotations (right and left) handle the case where the imbalance is on the "outside" of the tree — the heavy subtree is on the same side as the child that caused the imbalance. Double rotations (right-left and left-right) handle the "inside" case where the heavy subtree is on the opposite side of the child. All rotations preserve the inorder traversal of the tree, maintaining BST properties. The critical difference between insertion and deletion is that insertion needs at most one rotation while deletion may require O(log N) rotations at every level. The five deletion cases help determine whether a simple balance change suffices or whether a rotation is needed, with Case 1a and 1b being the simplest since they require no further checking beyond the parent node.

🧠 Quick Revision Questions

1. What is the difference between a single right rotation and a double right-left rotation, and when would you use each?
2. Why does deletion in an AVL tree potentially require more rotations than insertion?
3. In the singleRightRotation function, why is the height of k2 set before the height of k1?
4. What are the three cases of BST deletion that form the first step of AVL deletion?
5. In Deletion Case 1a, why does changing only the parent's balance suffice without checking higher nodes?

📘 Lecture 24 — Deletion in AVL Tree & Other Uses of Binary Trees

📖 Overview: This lecture completes the discussion of deletion in AVL trees by examining five distinct cases that arise when a node is removed. It also introduces other practical applications of binary trees, including expression trees, parse trees in compilers, and query trees in databases. Understanding deletion cases is critical for maintaining AVL tree balance, while expression trees form the foundation of compiler design and optimization.

🗂️ Topics Covered

The lecture covers the five cases of node deletion in AVL trees, each requiring specific actions including changing balance factors, single rotations, or double rotations. It then explores other uses of binary trees such as expression trees, parse trees for compilers and SQL queries, and how compilers perform optimization using common subexpression detection and graph conversion.

📝 Lecture Summary

Deletion in AVL Tree

When a node is deleted from an AVL tree, the tree can become unbalanced. The balance factor of each node is calculated and rotations are performed for unbalanced nodes. Unlike insertion where only one node's balance is adjusted, deletion may require rotation propagation all the way to the root node. There are five cases to consider, involving different balance factor values and subtree deletion locations.

🔑 Definition — Balance Factor: The height difference between left and right subtrees of a node. In AVL trees, acceptable values are -1, 0, or 1.

Case 1a: The parent of the deleted node had a balance of 0 and a node was deleted in the parent's left subtree.

After deletion, the balance changes from 0 to -1 (tilted toward right), which remains within AVL limits.

Action required: Change the balance of the parent node and stop. No further effect on balance of any higher node.

📌 Example: In a tree with root 4, nodes 2 and 6 at level 1, and nodes 1,3,5,7 at level 2, deleting node 1 tilts node 2 toward right (-1). The root node 4 remains unchanged. No rotation needed.

Case 1b: The parent of the deleted node had a balance of 0 and the node was deleted in the parent's right subtree.

Action required: Change the balance of the parent node and stop. No further effect on balance of any higher node (same as 1a).

Case 2a: The parent of the deleted node had a balance of 1 and the node was deleted in the parent's left subtree.

After deletion, the balance becomes 0, but this change may affect higher nodes.

Action required: Change the balance of the parent node. May have caused imbalance in higher nodes so continue up the tree.

Case 2b: The parent of the deleted node had a balance of -1 and the node was deleted in the parent's right subtree.

Action required: Change the balance of the parent node. May have caused imbalance in higher nodes so continue up the tree.

Case 3a: The parent had a balance of -1 and the node was deleted in the parent's left subtree, and the right subtree was balanced.

After deletion, the height of left subtree changes to h-1.

Action required: Perform single rotation, adjust balance. No effect on balance of higher nodes so stop here.

📐 Formula: Single rotation swaps parent A and child B — A becomes left subtree of B, and B's left subtree becomes A's right subtree.

Case 4a: Parent had a balance of -1 and the node was deleted in the parent's left subtree, and the right subtree was unbalanced.

Action required: Double rotation at B. May have affected the balance of higher nodes, so continue up the tree.

📐 Formula: Double rotation involves two rotations — first rotate the child, then rotate the parent. Node A becomes left child of new root B, node C becomes right child of new root B.

Case 5a: The parent had a balance of -1 and the node was deleted in the parent's left subtree, and the right subtree was unbalanced (with a different configuration than Case 4a).

Action required: Single rotation at B. May have affected the balance of higher nodes, so continue up the tree.

💡 Why this matters: The phrase "continue up the tree" appears in several cases. This is implemented using recursion — work to be done later is pushed onto the stack, deletion occurs when reaching the desired node, and rotation operations are performed while traversing back to the root node.

Symmetrical cases 3b, 4b, and 5b exist for deletion from the right subtree, which follow analogous patterns.

Other Uses of Binary Trees

A characteristic of binary trees is that values inside nodes on the left of a node are smaller than the node's value, and values on the right are greater.

For searching, binary trees require traversing up to log₂n levels maximum. AVL trees in the worst case require searching 1.44 log₂n levels.

Expression Trees

Expression trees, more general parse trees, and abstract syntax trees are significant components of compilers. They represent mathematical expressions in tree form where operators become internal nodes and operands become leaf nodes.

📌 Example: The expression (a+b*c)+((d*e+f)*g) is represented as a tree where b and c share a parent * node, a connects to + along with b*c, and the right subtree represents (d*e+f)*g with the root node being +.

Parse Tree in Compilers

A parse tree represents the syntactic structure of a programming language statement according to a grammar.

📌 Example: The assignment A := A + B * C is represented as a parse tree with root node <assign>, which has three parts: <id> (identifier A on left), assignment operator :=, and <expr> representing A + B * C on the right.

The parse tree expands through grammar rules:

• <assign> → <id> := <expr>
• <id> → A | B | C
• <expr> → <expr> + <term> | <term>
• <term> → <term> * <factor> | <factor>
• <factor> → <id>

Parsing is the process of reading and extracting the required structure. Compilers parse computer languages to form parse trees. Speech recognition and handwriting recognition also involve similar tree structures.

Parse Tree for an SQL Query

Parse trees are used in database query processing. Consider a database with tables:

• StarsIn(title, year, starName)
• MovieStar(name, address, gender, birthdate)

SQL query: SELECT title FROM StarsIn, MovieStar WHERE starName = name AND birthdate LIKE '%1960'

This query retrieves movie titles where actors were born in 1960. The database engine creates a tree with root <Query> that branches into SELECT, FROM, WHERE, and Condition subnodes, expanding downward to attributes and values.

Compiler Optimization

Compilers detect common subexpressions within parse trees — identical subtrees that appear multiple times.

📌 Example: In the expression (f+d*e) + ((d*e+f)*g), the subexpressions f+d*e and d*e+f are equivalent (commutative property of addition).

Instead of calculating common subexpressions again, compilers calculate them once and reuse them. The optimizer (part of the compiler) creates a directed acyclic graph (DAG) by connecting both paths to the same subtree. This graph has two or more different paths to reach a node, making it no longer a tree but a graph with directed edges.

💡 Why this matters: Converting expression trees to graphs for common subexpression elimination dramatically improves runtime efficiency by avoiding redundant calculations.

⭐ Key Takeaways

The five deletion cases in AVL trees are distinguished by the balance factor of the parent node (0, 1, or -1) and which subtree the deletion occurs in (left or right). Cases where the parent had balance 0 (1a and 1b) only require changing the balance factor without rotation, while cases 2a and 2b may require propagating balance adjustments upward through recursion. Cases 3a, 4a, and 5a require single or double rotations depending on whether the sibling subtree is balanced or unbalanced, with some cases requiring continuation up the tree and others stopping immediately. Beyond search trees, binary trees serve as expression trees and parse trees in compilers, databases, and speech recognition systems, with optimizers converting common subexpressions into directed acyclic graphs for efficiency.

🧠 Quick Revision Questions

1. In which deletion case(s) is no rotation required and only the balance factor of the parent node is changed?
2. What is the difference between Case 3a and Case 4a in terms of the sibling subtree's condition and the type of rotation required?
3. Why does deletion in AVL trees potentially require "continuing up the tree" while insertion typically only affects one node?
4. How does a compiler's optimizer convert an expression tree into a graph for common subexpression elimination?
5. What are the three main components of an assignment statement's parse tree in a compiler, and how do they correspond to the grammar rules?

📘 Lecture 25 — Expression Tree and Huffman Encoding

📖 Overview: This lecture continues the discussion on expression trees, demonstrating how to build them from postfix expressions using a stack. It also introduces Huffman Encoding, a data compression technique that uses binary trees to reduce the size of transmitted data by assigning variable-length codes based on character frequency.

🗂️ Topics Covered

The lecture first revisits expression trees, covering their structure with operators as inner nodes and operands as leaf nodes, then explains inorder traversal with parenthesis and postorder traversal to obtain postfix expressions. It presents a step-by-step algorithm to build an expression tree from a postfix expression using a stack. The second half introduces Huffman Encoding, discussing data compression, its importance in networking, and the algorithm to build a Huffman tree by combining character-frequency nodes.

📝 Lecture Summary

Expression tree

The lecture revisits expression trees, which are binary trees where inner nodes contain operators and leaf nodes contain operands. For binary operators like + and *, the tree is a binary tree, but unlike a Binary Search Tree (BST) , there is no sorting—the structure reflects operator precedence. Unary operators like negation (-) would produce a node with only one child.

The inorder traversal of an expression tree yields the infix expression, but without parentheses. For the tree shown, inorder traversal gives: a+b*c+d*e+f*g. To include parentheses, a modified inorder routine is used:

void inorder(TreeNode<int>* treeNode) 
{
    if( treeNode != NULL ){
        cout << "(";
        inorder(treeNode->getLeft());
        cout << ")";
        cout << *(treeNode->getInfo());
        cout << "(";
        inorder(treeNode->getRight());
        cout << ")";
    }
}

This routine places an opening parenthesis before traversing the left subtree and a closing parenthesis after, and similarly for the right subtree. Executing this on the example tree produces: ( a + ( b * c )) + ((( d * e ) + f ) * g ).

Postorder traversal of the same tree yields the postfix expression: a b c * + d e * f + g * +. In postfix form, no parentheses are needed because the operator order inherently defines precedence.

Building an Expression Tree

The algorithm to build an expression tree from a postfix expression is as follows:

1. Read a symbol from the postfix expression (left to right).
2. If the symbol is an operand, create a tree node for it and push it onto a stack.
3. If the symbol is an operator, pop two trees from the stack, create a new tree node with the operator as the root, make the first popped node the right subtree and the second popped node the left subtree, and push this new tree onto the stack.

The stack is implemented using templates so it can hold TreeNode objects.

Example: Building the tree for postfix expression a b + c d e + * *.

• Step 1: Read a (operand) → create node, push onto stack.
• Step 2: Read b (operand) → create node, push onto stack. Stack now has a, b.
• Step 3: Read + (operator) → pop a and b, create node + with left child a and right child b, push + node. Stack now has +.
• Step 4: Read c (operand) → create node, push onto stack.
• Step 5: Read d (operand) → create node, push onto stack.
• Step 6: Read e (operand) → create node, push onto stack. Stack now has +, c, d, e.
• Step 7: Read + (operator) → pop d and e, create node + with left child d and right child e, push + node. Stack now has +, c, +.
• Step 8: Read * (operator) → pop c and + (the one with d and e), create node * with left child c and right child +, push * node. Stack now has +, *.
• Step 9: Read * (operator) → pop the * node and the + node (the one with a and b), create node * with left child + and right child *, push final tree onto stack.

The final tree's inorder traversal (without parentheses) gives: a + b * c * d + e.

💡 Why this matters: This algorithm shows how compilers and interpreters can parse mathematical expressions from their postfix form into a tree structure for evaluation or code generation.

Huffman Encoding

Huffman Encoding is a data compression technique that uses a binary tree to assign variable-length codes to characters, where more frequent characters get shorter codes. Data compression is crucial in computer networks to reduce transmission time—either by increasing the data rate of the media or by sending less data without losing information.

Example: The phrase "traversing threaded binary trees" (33 characters including spaces and newline) normally requires 33 × 8 = 264 bits using ASCII. Huffman Encoding can represent it in only 116 bits, a saving of about 40%.

The Huffman algorithm:

1. List all characters used (including space and newline) along with their frequency in the message.
2. Consider each (character, frequency) pair as a node (these are the leaf nodes).
3. Pick the two nodes with the lowest frequency. In case of a tie, pick randomly.
4. Create a new parent node with these two as children, and assign it the sum of their frequencies.
5. Continue combining the two nodes of lowest frequency until only one node (the root) remains.

Example frequencies for the phrase:

• NL (newline): 1
• SP (space): 3
• a: 3
• b: 1
• d: 2
• e: 5
• g: 1
• h: 1
• i: 2
• n: 2
• r: 5
• s: 2
• t: 3
• v: 1
• y: 1

Building the tree: Nodes with frequency 1 (v, y, g, h, NL, b) are combined first into parent nodes of frequency 2. These are then combined with other low-frequency nodes (d, i, n, s) to form larger subtrees. Nodes a and t (frequency 3 each) combine into a parent of frequency 6. The SP node (frequency 3) combines with the v-y subtree (frequency 2) to form a parent of frequency 5. Finally, all subtrees combine into a root node with frequency 33.

🔑 Definition — Huffman Encoding: A method for compressing data by assigning variable-length binary codes to characters based on their frequency, where more frequent characters receive shorter codes, using a binary tree to generate the codes.

💡 Why this matters: Huffman Encoding is used in JPEG image compression, modem data compression, and file compression utilities like WinZip. It demonstrates how binary trees can solve real-world efficiency problems.

⭐ Key Takeaways

Expression trees encode mathematical expressions with operators as inner nodes and operands as leaves; traversing them in inorder (with parenthesis), preorder, or postorder yields infix, prefix, or postfix notation. The algorithm to build an expression tree from a postfix expression uses a stack: operands are pushed as nodes, and when an operator is encountered, two nodes are popped to form a new subtree with the operator as root. Huffman Encoding compresses data by using a binary tree where more frequent characters get shorter codes, significantly reducing transmission size. The Huffman tree is built by repeatedly combining the two lowest-frequency nodes into a parent node until a single root remains. This technique achieves about 40% compression for typical text and is foundational to modern compression standards.

🧠 Quick Revision Questions

1. In an expression tree, what type of data is stored in inner nodes versus leaf nodes?
2. How does the inorder traversal routine with parenthesis ensure correct operator precedence?
3. What are the steps of the algorithm to convert a postfix expression into an expression tree?
4. What is the primary goal of Huffman Encoding, and how does it achieve data compression?
5. In the Huffman algorithm, how is a parent node created from two child nodes, and what value does it store?

📘 Lecture 26 — Hoffman Encoding and Mathematical Properties of Binary Trees

📖 Overview: This lecture continues the discussion on Huffman encoding for data compression, demonstrating the complete process of building a Huffman tree from character frequencies and generating variable-length codes. It also introduces important mathematical properties of binary trees, particularly the relationship between internal and external nodes.

🗂️ Topics Covered

The lecture covers the complete Huffman encoding process including frequency counting, building a binary tree from bottom up using frequency nodes, assigning 0/1 to tree branches, generating variable-length codes, and compressing the message. It also discusses how the receiver decodes the message using the same tree, the use of priority queues in the algorithm, and modem compression techniques. Finally, it introduces mathematical properties of binary trees concerning internal and external nodes.

📝 Lecture Summary

Hoffman Encoding

In the previous lecture, we began discussing Huffman encoding for data compression. Huffman encoding is a method for compressing standard text documents by using a binary tree to develop codes of varying lengths for the letters used in the original message. It is also part of the JPEG image compression scheme, introduced by David Huffman in 1952.

The example uses the 32-character phrase: "traversing threaded binary trees". If sent using standard 8-bit ASCII codes, this would require 8 × 32 = 256 bits. However, the Huffman algorithm can reduce the message size to 116 bits.

The steps involved in Huffman encoding are:

1. List all letters used (including space character) along with their frequency in the message
2. Consider each (character, frequency) pair as a node (these become leaf nodes)
3. Pick two nodes with the lowest frequency (if there is a tie, pick randomly among those with equal frequencies)
4. Make a new node out of these two, making the two nodes its children
5. Assign this new node the sum of the frequencies of its children
6. Continue combining the two nodes of lowest frequency until only one node (the root) remains

In the example, the character frequencies from the phrase "traversing threaded binary trees" were counted (including NL for newline and SP for space). Characters with frequency 1 include NL, b, g, h, v, and y. Characters with frequency 2 include d, i, n, and s. Characters with frequency 3 include a, t, and SP. Characters with frequency 5 include e and r.

The process begins by joining nodes with the lowest frequency (1): v and y are joined, creating a parent node of frequency 2. Then g and h are joined (frequency 2), and NL and b are joined (frequency 2). Next, nodes with frequency 2 are joined: d and i create a node of frequency 4, and n and s create another node of frequency 4. Then a and t are joined to create a node of frequency 6. The process continues upward: SP joins with the parent of v and y (frequency 5), r joins with that node (frequency 10), e joins with a node of frequency 4 (frequency 9), and two nodes of frequency 4 combine to make frequency 8. Finally, nodes of frequency 6 and 8 combine to make 14, nodes of frequency 9 and 10 combine to make 19, and the root combines 14 and 19 to make frequency 33.

To generate codes, we start at the root and assign 0 to the left branch and 1 to the right branch, repeating this process down the left and right subtrees. To get the code for a character, we traverse the tree from the root to the character leaf node and read off the 0 and 1 along the path.

For example, to reach letter d from the root: go through node 14 (value 0), then to node 8 (value 1), then to node 4 on the left (value 0), then finally to d (value 0). Thus, the code for letter d is 0100. Similarly, the code for i is 0101.

🔑 Definition — Huffman Encoding: A data compression method that uses a binary tree to create variable-length codes for characters, where more frequent characters receive shorter codes and less frequent characters receive longer codes.

📌 Example: For the phrase "traversing threaded binary trees":

• Letter t has code 001 (3 bits)
• Letter r has code 110 (3 bits)
• Letter a has code 000 (3 bits)
• Letter v has code 11100 (5 bits)
• Letter e has code 101 (3 bits)

The encoded message becomes: 00111000011100101110011101010110100101111001100111101010000100101010011111000101010110000110111011111001110101101011110000

💡 Why this matters: The Huffman encoded message requires only 120 bits compared to 264 bits using ASCII encoding - a reduction of 54%. This means data transmission time is approximately halved.

Decoding Process

The receiver needs to know the codes used for each letter. The sender sends the tree structure to the receiver. When the receiver gets the encoded message, it starts at the root and processes each bit: if the bit is 0, go left; if the bit is 1, go right. Upon reaching a leaf node (where both left and right links are NULL), the receiver knows that character has been received. The receiver then returns to the root and continues with the next bit to find the next character, repeating the process until the entire message is decoded.

Priority Queue in Huffman Encoding

Instead of randomly choosing nodes with equal frequencies, a priority queue can be used. Characters are placed in the queue according to their frequencies, with the lowest frequency at the front. Two nodes are removed from the queue, joined to create a parent node with the sum of their frequencies, and this new node is inserted back into the queue according to its frequency. This process continues until the queue is empty, and the last remaining node is the root.

Mathematical Properties of Binary Trees

A binary tree of N internal nodes has N + 1 external nodes. Internal nodes include all nodes with data (including leaf nodes). External nodes are NULL pointers - positions where nodes could potentially exist but currently do not. In the figure shown, there are 9 internal nodes (A, B, C, D, E, F, G plus two others) and 10 external nodes (represented by squares), confirming the property that external nodes = internal nodes + 1.

🔑 Definition — External node: A NULL pointer position in a binary tree where a node could potentially exist. These are not actual data nodes but represent the children of leaf nodes that are NULL.

📐 Formula: For a binary tree with N internal nodes, the number of external nodes = N + 1

⭐ Key Takeaways

The most critical concepts to remember are: (1) Huffman encoding creates variable-length codes where more frequent characters get shorter codes, achieving data compression; (2) the tree is built bottom-up by repeatedly joining the two nodes with lowest frequencies until one root remains; (3) codes are generated by assigning 0 to left branches and 1 to right branches, then reading the path from root to leaf; (4) the encoded message requires significantly fewer bits than ASCII encoding (54% reduction in the example); and (5) in any binary tree, the number of external nodes always equals the number of internal nodes plus one.

🧠 Quick Revision Questions

1. What are the six steps involved in building a Huffman encoding tree from a text message?
2. How do you generate the code for a specific character once the Huffman tree is built with 0/1 branch assignments?
3. Why do letters with higher frequency get shorter codes in Huffman encoding?
4. How does the receiver decode a Huffman-encoded message without knowing the code table in advance?
5. State the mathematical property relating internal nodes and external nodes in a binary tree.

📘 Lecture 27 — Properties of Binary Tree

📖 Overview: This lecture covers two main topics: the mathematical properties of binary trees regarding internal and external nodes/links, and the concept of threaded binary trees. The threaded tree modification is important because it allows stack-free inorder traversal, eliminating the overhead of recursive calls and explicit stack operations during repeated traversals.

🗂️ Topics Covered

The lecture begins by discussing the second property of binary trees concerning link counts (2N total links, N-1 internal links, N+1 external links). It then introduces threaded binary trees as a solution to the costly overhead of stack operations during recursive traversals. The process of adding threads during insertion is explained with code and diagrams, followed by how to find the inorder successor in a threaded tree. Finally, a non-recursive, stack-free inorder traversal routine is presented.

📝 Lecture Summary

Properties of Binary Tree

A binary tree with N internal nodes has 2N links total. Of these, N-1 links connect internal nodes to other internal nodes, and N+1 links connect internal nodes to external nodes (NULL pointers). This is a mathematical property that can be proven.

🔑 Definition — Internal Node: A node that has at least one child. Leaf nodes are also considered internal nodes in this context. 🔑 Definition — External Node: A NULL pointer or square node representing an absent child. 📐 Formula: 2N = (N-1) + (N+1) → In a tree with N internal nodes, total links are 2N, internal-to-internal links are N-1, and links to external nodes are N+1. 📌 Example: In a tree with 9 internal nodes (marked A-I), there are 8 internal links and 10 external links. Total = 18 = 2 × 9.

💡 Why this matters: These properties help understand the number of NULL pointers available in a binary tree, which is the foundation for threaded binary trees.

Threaded Binary Trees

In many applications, binary tree traversals are carried out repeatedly. The overhead of stack operations during recursive calls can be costly. The same would be true if we use a non-recursive but stack-driven traversal procedure. So, we modify the tree data structure to speed up inorder traversal and make it "stack-free."

🔑 Definition — Threaded Binary Tree: A binary tree where NULL pointers are replaced with pointers to the inorder successor (or predecessor) of a node.

Most pointer fields in a standard binary tree representation are NULL. Since every node (except the root) is pointed to, there are only N-1 non-NULL pointers out of a possible 2N (for an N node tree), so that N+1 pointers are NULL.

In a threaded tree, these NULL pointers are replaced with pointers to the inorder successor (or predecessor) as appropriate. We need to know whenever formerly NULL pointers have been replaced by non-NULL pointers to successor/predecessor nodes, since otherwise there's no way to distinguish those pointers from the customary pointers to children.

🔑 Definition — LTH / RTH flags: Boolean flags in each node that indicate whether the left/right pointer is a thread (pointing to predecessor/successor) or a child pointer. If the flag is "child," the pointer is a normal tree link. If the flag is "thread," the pointer is a thread to the inorder predecessor or successor.

Adding Threads During Insert

When inserting a new node into a threaded binary tree, we must set the threads correctly.

Consider inserting node 16 into a tree containing nodes 14, 15, 18, and 20. The inorder sequence would be: 14, 15, 16, 18, 20.

The code to insert node 16 as the left child of node 18 (pointed to by p) is:

1. t->L = p->L;     // copy the thread (predecessor of 18 was 15, now becomes predecessor of 16)
2. t->LTH = thread; // mark left pointer as thread
3. t->R = p;        // *p (18) is successor of *t (16)
4. t->RTH = thread; // mark right pointer as thread
5. p->L = t;        // attach the new leaf as left child of 18
6. p->LTH = child;  // mark left pointer as child (not a thread)

📌 Example: Before insertion, node 18's left pointer was a thread pointing to node 15 (its predecessor). After insertion, node 16's left pointer is set to the thread (now pointing to 15), and node 16's right pointer is set to point to node 18 (its successor). Node 18's left pointer is then changed to point to node 16 as its actual left child.

Where is Inorder Successor?

For any node in a binary tree, the inorder successor is the leftmost node in the right subtree of that node.

To find the inorder successor:

1. If the node has a right thread (RTH == thread), the successor is simply the node pointed to by the right pointer.
2. Otherwise (RTH == child), go to the right child, then follow left child pointers until you reach a node whose left pointer is a thread (LTH == thread).

📌 Example: For node 4, its inorder successor is 5. We go to node 9 (right child of 4), then to node 7, then to node 5 (the leftmost node in the right subtree of 4, and also the leaf node whose left pointer is a thread).

Inorder Traversal

Using the nextInorder routine, we can implement a non-recursive, stack-free inorder traversal.

TreeNode* nextInorder(TreeNode* p) {
    if (p->RTH == thread)
        return (p->R);
    else {
        p = p->R;
        while (p->LTH == child)
            p = p->L;
        return p;
    }
}

If we call nextInorder with the root of the tree, we have some difficulty. The code won't work properly because we need to find the first node to print (the leftmost node in the tree). The lecture indicates a small change is needed to handle the root case.

📌 Example: Starting at root node 14, if we call nextInorder(14), the right pointer is not a thread (it points to child 15), so we go to the else part. We set p = 15 (right child), then try to follow left pointers, arriving at the wrong node. We need to start at the leftmost node first.

⭐ Key Takeaways

The critical student must remember that a binary tree with N internal nodes has 2N total links, N-1 internal-to-internal links, and N+1 links to external nodes (NULL pointers). Threaded binary trees repurpose these NULL pointers to point to inorder successors and predecessors, enabling stack-free traversal. Two flags (LTH and RTH) are essential to distinguish threads from child pointers. The inorder successor of any node is found by going to its right child and then following left children until a thread is encountered. The nextInorder routine can then be called repeatedly in a loop for complete stack-free inorder traversal, though root handling requires special attention.

🧠 Quick Revision Questions

1. What is the relationship between internal nodes and external links in a binary tree?
2. Why is a "stack-free" traversal desirable, and how do threaded binary trees achieve it?
3. What is the purpose of the LTH and RTH flags in a threaded binary tree node?
4. How do you find the inorder successor of a node in a threaded binary tree?
5. What potential problem arises when calling nextInorder with the root node of a threaded tree?

📘 Lecture 28 — Inorder Traversal in Threaded Trees & Complete Binary Tree

📖 Overview: This lecture continues the discussion of inorder traversal in threaded binary trees, presenting a solution to the problem of incorrect traversal using a dummy node trick. It then introduces the concept of complete binary trees, their properties, and how they can be efficiently stored in an array without pointers.

🗂️ Topics Covered

The lecture covers two main topics: first, fixing the nextInorder routine for threaded binary trees by adding a dummy node to ensure correct traversal direction, along with the fastInorder routine that uses this trick. Second, it introduces the complete binary tree definition, its height and node count properties, and the array storage scheme using the 2i and 2i+1 indexing rule, with examples showing level-order traversal correspondence.

📝 Lecture Summary

Inorder traversal in threaded trees

The nextInorder routine is designed to find the inorder successor of a node in a threaded binary tree. It first checks if the right pointer of the node is a thread — if so, it returns the right pointer as it points to the inorder successor. Otherwise, it moves to the right child and then follows left children until it finds a node whose left pointer is a thread.

TreeNode* nextInorder(TreeNode* p){
    if(p->RTH == thread) return(p->R);
    else {
        p = p->R;
        while(p->LTH == child)
            p = p->L;
        return p;
    }
}

When this routine is applied to the sample tree by passing the root node (14), it does not work properly. The pointer moves to node 15 (the right child of root) instead of going to the leftmost node (3) first. This is because the routine checks the right pointer first, which for the root is a link, causing movement in the wrong direction for inorder traversal.

💡 Why this matters: The routine fails because it cannot distinguish between being at the root node (where left traversal is needed first) versus being at an internal node. A programming trick is needed to fix this.

To fix this problem, a dummy node is inserted into the tree. The dummy node has:

• Its left pointer pointing to the root node of the tree
• Its right pointer pointing to itself (the dummy node)
• The left thread of the leftmost node points to the dummy node
• The right thread of the rightmost node points to the dummy node

void fastInorder(TreeNode* p)
{
    while((p = nextInorder(p)) != dummy) 
        cout << p->getInfo();
}

The fastInorder routine is called with the dummy node as argument: fastInorder(dummy). Starting from the dummy node, the routine correctly traverses to the leftmost node first. The pointer moves from dummy → node 14 → node 4 → node 3 (where left pointer is a thread), returning node 3 as the first inorder element. Subsequent calls follow threads and links correctly to produce the complete inorder traversal without recursion.

🔑 Definition — Dummy node: An extra node inserted into a threaded binary tree whose left pointer points to the root, right pointer points to itself, and left/right threads of extreme nodes point to it, enabling correct inorder traversal from a known starting point.

📐 Formula: fastInorder(dummy) → starts traversal at the dummy node, which leads to the leftmost node first, producing correct inorder sequence.

📌 Example: From the sample tree with dummy node, calling nextInorder(dummy) moves p from dummy → 14 → 4 → 3 (thread found, return 3). Next call with p=3 follows the right thread to node 4. Next call with p=4 follows the right link to node 9, then left to node 5, etc. The full inorder sequence produced is: 3, 4, 5, 7, 9, 14, 15, 16, 18, 20.

Complete Binary Tree

A complete binary tree is defined by two properties:

• A tree that is completely filled, with the possible exception of the bottom level
• The bottom level is filled from left to right

In a complete binary tree, all nodes except those at the bottom level have both left and right children. At the bottom level, leaf nodes appear from left to right, but the level may not be completely filled.

🔑 Definition — Complete binary tree: A binary tree where all levels are completely filled except possibly the last level, which is filled from left to right.

Properties of complete binary trees:

• A complete binary tree of height h has between 2^h to 2^(h+1) – 1 nodes
• The height of such a tree is floor(log₂N) where N is the number of nodes
• Because the tree is so regular, it can be stored in an array — no pointers are necessary

📐 Formula — Array indexing for complete binary tree: For any array element at position i, the left child is at 2i, the right child is at (2i + 1), and the parent is at floor(i/2).

💡 Why this matters: Array storage starts at position 1 (not 0) because if position were 0, then 2i would also be 0, making it impossible to distinguish the root from its children. Position 0 is ignored.

📌 Example: Consider the tree nodes A(1), B(2), C(3), D(4), E(5), F(6), G(7), H(8), I(9), J(10).

• Root A at position 1 → left child B at 2(1)=2, right child C at 2(1)+1=3 ✓
• Node B at position 2 → left child D at 2(2)=4, right child E at 2(2)+1=5 ✓
• Node C at position 3 → left child F at 2(3)=6, right child G at 2(3)+1=7 ✓
• Node D at position 4 → left child H at 2(4)=8, right child I at 2(4)+1=9 ✓
• Node E at position 5 → left child J at 2(5)=10, right child at 2(5)+1=11 (empty) ✓
• Node J at position 10 → parent at floor(10/2)=5 (node E) ✓
• Node I at position 9 → parent at floor(9/2)=4 (node D) ✓

The level-order traversal of the tree directly gives the indices for array storage. The order is: A(1), B(2), C(3), D(4), E(5), F(6), G(7), H(8), I(9), J(10). These numbers correspond exactly to the array indices when using the 2i scheme.

Comparison: Pointers vs. Arrays for tree storage:

• Arrays are fast and efficient, supported directly by the language compiler
• Pointers can cause problems with paging (virtual memory), where loading/unloading code segments slows execution
• Use arrays whenever they can fulfill requirements; use pointers only where beneficial (e.g., AVL tree balancing where moving large data in arrays would be inefficient)

⭐ Key Takeaways

The inorder traversal problem in threaded trees is solved by inserting a dummy node that points to the root, allowing the nextInorder routine to start correctly and traverse to the leftmost node first. The fastInorder routine using this trick produces correct inorder traversal without recursion or stack, making it faster than recursive traversal. A complete binary tree is a regular structure where all levels are filled except possibly the bottom level, which is filled left to right. Such trees can be stored efficiently in an array using the 2i and 2i+1 indexing scheme, where position 1 holds the root. This array storage eliminates the need for pointers, leveraging the compiler's native support for arrays to improve performance and avoid paging issues. The level-order traversal directly corresponds to the array index positions, making storage straightforward.

🧠 Quick Revision Questions

1. What is the main problem with the original nextInorder routine when called with the root node, and how does the dummy node trick fix it?

2. In the fastInorder routine, why is the function called with the dummy node as argument instead of the root? Trace the first two steps of traversal starting from the dummy node.

3. State the definition of a complete binary tree and list its two key properties regarding height and number of nodes.

4. Given a complete binary tree stored in an array using the 2i and 2i+1 scheme starting at position 1, find the left child, right child, and parent of the node at position 6. Show the calculations.

5. Why does array storage for complete binary trees start at position 1 instead of position 0? What would happen if we used position 0 as the starting point?

📘 Lecture 29 — Data Structures

📖 Overview: This lecture introduces the heap data structure, a complete binary tree that follows the heap order property. It explains how heaps are stored efficiently using arrays, distinguishes between min heaps and max heaps, and demonstrates the insertion algorithm for maintaining heap order after adding new elements. Understanding heaps is essential for implementing priority queues and efficient sorting algorithms.

🗂️ Topics Covered

The lecture covers the storage of complete binary trees in arrays using the 2i and 2i+1 scheme, explains why arrays are unsuitable for incomplete trees due to memory wastage, defines the heap data structure with its heap order property, distinguishes between min heaps and max heaps, and provides a detailed step-by-step demonstration of inserting a new value into a min heap while preserving the heap property through upward swapping.

📝 Lecture Summary

Complete Binary Tree

In the previous lecture, we discussed storing a complete binary tree in an array using the 2i and 2i+1 scheme. This scheme allows a programmer to navigate from a parent to its children and from children back to the parent. Arrays are efficient built-in data structures in many languages.

💡 Why this matters: Arrays are only efficient for complete binary trees because they can be stored contiguously without wasting space. For incomplete trees, the array would have "holes" (empty positions), leading to memory wastage.

The 2i scheme stores the left child of node at index i at position 2i, and the right child at position 2i+1. When a tree is not complete, we would need to treat it as complete by imagining missing nodes exist, then remove the data at those positions afterward — leaving empty holes in the array.

🔑 Definition — Complete Binary Tree: A binary tree in which all levels are completely filled except possibly the last level, which is filled from left to right.

Heap

Heap is a data structure of significant use and benefit. It is primarily used in priority queues. Recall the bank simulation example where events were placed in a priority queue that does not follow FIFO rules — elements are retrieved based on their priority rather than insertion order.

💡 Why this matters: Implementing priority queues with arrays requires sorting and shifting elements, which is expensive in terms of time. The heap provides a much more efficient alternative for priority queue operations.

The heap data structure is defined as:

"A heap is a complete binary tree that conforms to the heap order."

The heap order property states that in a min heap, for every node X, the key in the parent is smaller than or equal to the key in X. In other words, the parent node has a key smaller than or equal to both of its children nodes.

This differs from a binary search tree (BST), where the left child is smaller and the right child is larger than the parent. In a heap, both children must be greater than the parent, but there is no ordering relationship between the left and right children themselves.

🔑 Definition — Heap Order: For a min heap, the value of every parent node is less than or equal to the values of its children nodes.

📌 Example: In the min heap shown, node 13 has children 21 and 16 — both are greater than 13. Node 21 has children 24 and 31 — both greater than 21. Node 16 has children 19 and 68 — both greater than 16. This pattern holds for every node.

In a min heap, the root node contains the smallest value in the entire tree. An inorder traversal of a heap does NOT produce sorted output, confirming it is not a binary search tree.

Max Heap

In a max heap, each node has a value greater than or equal to the values of its left and right children. Consequently, the root node contains the largest value, and values become smaller at lower levels.

By repeatedly removing the root from a min heap and allowing the remaining values to adjust themselves into a heap again, we get the smallest value each time. Continuing this process yields data in ascending order — this is the basis of heap sort.

Similarly, a max heap can be used for priority queues where the highest priority element is always at the top.

🔑 Definition — Max Heap: A complete binary tree where every parent node has a value greater than or equal to the values of its children.

Insertion in a Heap

When inserting a new value into a heap, we need to:

1. Place the new node at a position that maintains the complete binary tree property (the next available position in level-order)
2. Then adjust upward to preserve the heap order property

📌 Example — Inserting value 14 into an existing min heap:

Step 1: The existing heap has values stored in an array at positions 1-10: 13, 21, 16, 24, 31, 19, 68, 65, 26, 32. Position 11 is empty.

Step 2: Add node 14 at position 11 (right child of node 31 at position 5). The tree remains complete binary.

Step 3: Check heap order. Compare 14 with its parent (31 at position 5). Since 14 < 31, the heap property is violated. Exchange them — 14 goes to position 5, 31 goes to position 11.

Step 4: Now compare 14 (at position 5) with its new parent (21 at position 2). Since 14 < 21, exchange them — 14 goes to position 2, 21 goes to position 5.

Step 5: Compare 14 (at position 2) with its new parent (13 at position 1). Since 13 < 14, the heap property is preserved. The insertion is complete.

The final array is: 13, 14, 16, 24, 21, 19, 68, 65, 26, 32, 31.

To find the parent of any node at position i, use the formula: floor(i / 2).

📌 Example — Inserting value 15 into the new heap:

Step 1: The new heap has values at positions 1-11. Position 12 is empty. Add node 15 as the left child of node 19 (at position 6), so position 12.

Step 2: Compare 15 with parent (19 at position 6). Since 15 < 19, exchange — 15 goes to position 6, 19 goes to position 12.

Step 3: Compare 15 (at position 6) with new parent (16 at position 3). Since 15 < 16, exchange — 15 goes to position 3, 16 goes to position 6.

Step 4: Compare 15 (at position 3) with new parent (13 at position 1). Since 13 < 15, the heap property is preserved. Done.

The final array is: 13, 14, 15, 24, 21, 16, 68, 65, 26, 32, 31, 19.

📐 Formula: parent(i) = floor(i / 2) — used to find the parent's position when traversing upward during insertion.

💡 Why this matters: The upward-swapping algorithm efficiently maintains heap order without requiring full sorting. Each comparison moves the new value one level up, so the worst-case time complexity is O(log n), where n is the number of nodes in the heap.

⭐ Key Takeaways

The heap is a complete binary tree stored efficiently in an array using the 2i and 2i+1 scheme, which eliminates memory wastage and pointer overhead. The heap order property distinguishes min heaps (parent smaller than children) from max heaps (parent larger than children). Insertion into a heap involves first placing the new element at the next available position to maintain the complete tree property, then repeatedly swapping it with its parent until the heap order is restored — a process called "percolating up" or "bubbling up." The parent of any node at position i is found using floor(i/2), making upward traversal straightforward in the array. The heap data structure is fundamental for implementing priority queues and heap sort algorithms.

🧠 Quick Revision Questions

1. What are the two essential properties that define a heap data structure?
2. Why is an array inefficient for storing an incomplete binary tree?
3. In a min heap with values 10, 25, 15, 30, 20, 40, 35, what is the value at the root and which values could be the children of 25?
4. If you insert the value 8 into the min heap 13, 21, 16, 24, 31, 19, 68, trace the steps showing which values are swapped and what the final heap looks like in the array.
5. Using the formula floor(i/2), determine the parent positions of nodes at indices 5, 9, and 12 in an array-based heap.

📘 Lecture 30 — Inserting into a Min-Heap, Deleting from a Min-Heap, Building a Heap

📖 Overview: This lecture covers fundamental heap operations in data structures. It explains how to insert elements into a min-heap while maintaining the heap order, how to delete the minimum element (deleteMin), and how to efficiently build a heap from an unordered array using the percolateDown method.

🗂️ Topics Covered

The lecture covers three main topics: inserting into a min-heap using the percolate-up technique where new elements are placed at the bottom and moved upward; deleting from a min-heap (deleteMin) where the root is removed and a hole percolates downward; and building a heap using the percolateDown method starting from position N/2 to achieve linear time complexity instead of Nlog₂N.

📝 Lecture Summary

Inserting into a Min-Heap

When inserting a new element into a min-heap implemented with an array, the element is placed at the last position of the array. Since this insertion may violate the heap order (where parent values must be less than children values), we start moving this element upward. Only one branch of the tree is affected due to this upward movement, making the process localized.

🔑 Definition — Min-Heap: A complete binary tree where the minimum value is always at the root, and every parent node has a value less than or equal to its children.

📐 Formula: Parent-child relationship in array → parent at position i, left child at 2i, right child at 2i+1

📌 Example: Inserting element 15 into a min-heap:

• Initial array: [13, 14, 16, 24, 21, 19, 68, 65, 26, 32, 31] (positions 1-11)
• Insert 15 at position 12 (left child of node at position 6, which is 19)
• Step 1: Compare 15 with parent 19 → 15 < 19, so swap (15 goes to position 6, 19 goes to position 12)
• Step 2: Compare 15 with new parent 16 → 15 < 16, so swap (15 goes to position 3, 16 goes to position 6)
• Step 3: Compare 15 with parent 13 → 15 > 13, so stop
• Final position: 15 is at position 3, maintaining min-heap order

💡 Why this matters: The maximum number of exchanges is log₂N, making insertion efficient even for large trees.

Deleting from a Min-Heap (deleteMin)

The deleteMin operation finds and removes the minimum number from the tree. Finding the minimum is easy because it is at the top of the heap (the root). Deletion causes a hole which needs to be filled while maintaining the complete binary tree property.

🔑 Definition — Percolate Down: The process where a hole moves downward in the tree, with smaller children moving upward to fill the hole, maintaining the min-heap order.

📌 Example: Deleting the minimum element from a min-heap:

• Initial tree: root = 13, children = 14 and 16
• Step 1: Remove root (13), creating a hole at position 1
• Step 2: Compare children 14 and 16 → 14 is smaller, so place 14 in the hole (position 1)
• Step 3: Hole now at previous position of 14. Compare its children 24 and 21 → 21 is smaller, so place 21 in the hole
• Step 4: Hole now at previous position of 21. Compare its children 32 and 31 → 31 is smaller, so place 31 in the hole
• Step 5: Hole has reached the bottom and can be deleted. Array size is reduced by 1

💡 Why this matters: The hole follows the 2i or 2i+1 scheme, moving from top to bottom until it reaches a position where it can be safely removed.

Building a Heap (buildHeap)

When given N keys, instead of doing N successive inserts (which could take Nlog₂N time in worst case), we can build a heap in linear time using the percolateDown method.

🔑 Definition — buildHeap: An algorithm that constructs a heap from an unordered array of N keys by applying percolateDown from position N/2 down to 1.

📐 Formula: Algorithm → for(i = N/2; i > 0; i--) percolateDown(i);

📌 Example: Building a min-heap from initial data of 15 elements:

• Initial array (positions 1-15): [65, 31, 32, 26, 21, 19, 68, 13, 24, 15, 14, 16, 5, 70, 12]
• Start with i = 15/2 = 7 (position 7 has value 68)
  • Children of position 7: positions 14 (70) and 15 (12)
  • Apply percolateDown(7): 12 is smaller than 68, so swap → position 7 becomes 12, position 15 becomes 68
• Next iteration: i = 6 (position 6 has value 19)
  • Children of position 6: positions 12 (16) and 13 (5)
  • Apply percolateDown(6): 5 is smaller than 19, so swap → position 6 becomes 5, position 13 becomes 19
• Continue until i = 1 is reached

🔑 Definition — PercolateDown(p): A method that moves the key in node p downward to its correct position in the min-heap, with smaller values moving upward automatically.

💡 Why this matters: This algorithm achieves linear time O(N) instead of O(Nlog₂N), making it significantly more efficient for large datasets.

⭐ Key Takeaways

For the exam, you must understand that insertion in a min-heap involves placing the new element at the bottom and percolating it upward until the heap order is restored, affecting only one branch of the tree with maximum log₂N exchanges. The deleteMin operation is straightforward — you remove the root (minimum element), create a hole, and percolate the hole downward by comparing children and moving the smaller one up, continuing until the hole reaches the bottom where it can be deleted. The critical insight for building a heap is that starting from position N/2 and applying percolateDown gives linear time complexity O(N) rather than Nlog₂N, with the loop moving through all non-leaf nodes from bottom to top. Remember that the parent-child relationship in the array uses the 2i and 2i+1 scheme for children, and i/2 for parent.

🧠 Quick Revision Questions

1. When inserting an element into a min-heap, at which position in the array is the new element initially placed?
2. In the deleteMin operation, what fills the hole created at the root, and how does the hole move through the tree?
3. Why does the buildHeap algorithm start the percolateDown loop from position N/2 instead of N?
4. What is the worst-case time complexity of building a heap using N successive inserts, and what is the time complexity using the percolateDown method?
5. In the percolateDown method, if a node has two children, which child is moved upward to fill the hole?

📘 Lecture 31 — Data Structures Lecture No. 31

📖 Overview: This lecture focuses on the BuildHeap algorithm, a more efficient method for constructing a heap from an existing dataset compared to repeated insert() calls. It also covers other essential heap operations like decreaseKey, increaseKey, and remove, and presents the complete C++ implementation of the Heap class, including the constructor, insert, and deleteMin methods.

🗂️ Topics Covered

This lecture covers the rationale and step-by-step execution of the BuildHeap algorithm, demonstrating how it transforms an unordered binary tree into a min-heap using the percolateDown procedure. It then introduces other important heap methods, including decreaseKey, increaseKey, and remove, explaining their utility, especially in the context of priority queues. The lecture concludes with a detailed walkthrough of the C++ code for the Heap class, covering the constructor, insert, and deleteMin methods.

📝 Lecture Summary

BuildHeap

In the previous lecture, we discussed the BuildHeap method of the heap abstract data structure. In this handout, you are going to know why a programmer adopts this method. Suppose we have some data that can be numbers or characters or in some other form and want to build a min-heap or max-heap out of it. One way is to use the insert() method to build the heap by inserting elements one by one. In this method, the heap property will be maintained. However, the analysis shows that it is NlogN algorithm i.e. the time required for this will be proportional to NlogN. Secondly, if we have all the data ready, then it will be better to build a heap at once as it is a better option than NlogN.

In the delete procedure, when we delete the root, a new element takes the place of root. In case of min-heap, the minimum value will come up and the larger elements will move downwards. In this regard, percolate procedures may be of great help. The percolateDown procedure will move the smaller value up and bigger value down. This way, we will create the heap at once, without calling the insert() method internally. Let’s revisit it again:

• The general algorithm is to place the N keys in an array and consider it to be an unordered binary tree.
• The following algorithm will build a heap out of N keys.

for ( i = N/2; i > 0; i-- )
    percolateDown(i);

Suppose, there are N data elements (also called as N Keys). We will put this data in an array and call it as a binary tree. As discussed earlier, a complete binary tree can be stored in an array. We have a tree in an array but it is not a heap yet. It is not necessary that the heap property is satisfied. In the next step, we apply the algorithm. Why did we start the i from N/2?

🔑 Definition — BuildHeap: A method to construct a heap from an unordered array of N keys by applying percolateDown() on each internal node, starting from the last internal node (at index N/2) up to the root.

📐 Formula:

for ( i = N/2; i > 0; i-- )
    percolateDown(i);

→ This loop starts at the last non-leaf node and moves up to the root, ensuring each subtree becomes a valid heap.

📌 Example: Build a min-heap from the array: [0, 65, 31, 32, 26, 21, 19, 68, 13, 24, 15, 14, 16, 5, 70, 12] (index 0 is unused, N=15).

1. Step 1 (i = N/2 = 7): percolateDown(7).
   • Node at index 7 is 68. Its children are 70 (index 14) and 12 (index 15).
   • 12 is the smallest. Swap 68 and 12.
   • Subtree with root 12 now satisfies the min-heap property.
2. Step 2 (i = 6): percolateDown(6).
   • Node at index 6 is 19. Its children are 16 (index 12) and 5 (index 13).
   • 5 is the smallest. Swap 19 and 5.
3. Step 3 (i = 5): percolateDown(5).
   • Node at index 5 is 21. It may be swapped with a smaller child.
4. Continue for i = 4, 3, 2, 1.
5. Final min-heap array: [0, 5, 13, 12, 24, 14, 16, 65, 26, 31, 15, 21, 32, 19, 70, 68]. The root is the minimum element (5).

Why start from N/2? All leaf nodes (indices > N/2) are already valid min-heaps by themselves (they have no children). Starting from N/2, the first level above the leaves, avoids unnecessary work on leaf nodes and makes the algorithm more efficient. The complexity of BuildHeap is O(N), which is better than the O(N log N) of N insert operations.

💡 Why this matters: The BuildHeap algorithm demonstrates that if you have all your data upfront, you can construct a heap more efficiently than inserting elements one by one. This is a classic example of how a clever algorithm can improve time complexity.

Other Heap Methods

Let’s have a look on some more methods of heap and see the C++ codes.

decreaseKey(p, delta) This method lowers the value of the key at position ‘p’ by the amount ‘delta’. Since this might violate the heap order, so it (the heap) must be reorganized with percolate up (in min-heap) or down (in max-heap).

This method takes a pointer to the node that may be the array position as we are implementing it as an array internally. The user wants to decrease the value of this node by delta. Suppose we have a node with value 17 and want to decrease it by 10. Its new value will be 10. By decreasing the value of a node, the heap order can be violated. If heap order is disturbed, then we will have to restore it. We may not need to build the whole tree. The node value may become smaller than that of the parents, so it is advisable to exchange these nodes. We use percolateUp and percolateDown methods to maintain the heap order. Here the question arises why we want to decrease the value of some node? The major use of heap is in priority queues. Priority queues are not FIFO or LIFO. The elements are taken out on some key value, also known as priority value. Suppose we have some value in the priority queue and want to decrease its priority. If we are using heap for the priority queue, the priority of the some elements can be decreased so that it could be taken out later and some other element that now has higher priority will be taken out first.

increaseKey(p, delta) This method is the opposite of decreaseKey. It will increase the value of the element by delta. These methods are useful while implementing the priority queues using heap.

remove(p) This method removes the node at position p from the heap. This is done first by decreaseKey(p, -∞) and then performing deleteMin(). First of all, we will decrease the value of the node by -∞ and call the method deleteMin. The deleteMin method deletes the root. If we have a min-heap, the root node contains the smallest value of the tree. After deleting the node, we will use the percolateDown method to restore the order of the heap.

The user can delete any node from the tree. We can write a special procedure for this purpose. Here we will use the methods which are already available. At first, the decreaseKey method will be called and value of node decreased by -∞. It will result in making the value of this node smallest of all the nodes. If the value is in integers, this node will have the smallest integer. Now this node has the minimum value, so it will become the root of the heap. Now we will call the deleteMin() and the root will be deleted which is the required node. The value in this node is not useful for us. The -∞ is a mathematical notation. It is not available in the C++. Actually we want to make the minimum possible value of this node supported by the computer.

C++ Code

Now we will look at the C++ code of the Heap class.

Heap.h file

/* The heap class. This is heap.h file */
template <class eType>
class Heap
{
public:
    Heap( int capacity = 100 );
    Void insert( const eType & x );
    Void deleteMin( eType & minItem );
    Const eType & getMin( );
    Bool isEmpty( );
    Bool isFull( );
    int  Heap<eType>::getSize( );

private:
    int  currentSize; // Number of elements in heap
    eType* array; // The heap array
    int    capacity;

    void percolateDown( int hole );
};

We may like to store different type of data in the heap like integers, strings, floating-point numbers or some other data type etc. For this purpose, template is used. With the help of template, we can store any type of object in the heap. Therefore first of all we have:

template <class eType>

Here eType will be used as a type parameter. We can use any meaningful name. Then we declare the Heap class. In the public part of the class, there is a constructor as given below.

Heap( int capacity = 100 );

We have a parameter capacity in the constructor. Its default value is 100. If we call it without providing the parameter, the capacity will be set to 100. If we call the constructor by providing it some value like 200, the capacity in the Heap object will be 200.

Next we have an insert method as: void insert( const eType & x );

Here we have a reference element of eType which is of constant nature. In this method, we will have the reference of the element provided by the caller. The copy of element is not provided through this method. We will store this element in the Heap.

Similarly we have a delete method as: void deleteMin( eType & minItem ); This method is used to delete the element from the heap.

If we want to know the minimum value of the heap, the getMin method can be useful. The signature is: const eType & getMin( ); This method will return the reference of the minimum element in the Heap.

We have some other methods in the Heap class to check whether it is empty or full. Similarly, there is a method to check its size.

bool isEmpty( ); bool isFull( ); int Heap<eType>::getSize( );

When will Heap become full? As we are implementing the Heap with the help of an array, the fixed data type, so the array may get full at some time. This is the responsibility of the caller not to insert more elements when the heap is full.

In the private part, we have some data elements and methods. At first, we have currentSize element. It will have the number of elements in the heap. Then we have an array of eType. This array will be dynamically allocated and its size depends on the capacity of the Heap. We have one private method as percolateDown.

Heap.cpp file

/* heap.cpp file */
#include "Heap.h"
template <class eType>
Heap<eType>::Heap(  int capacity )
{
    array = new eType[capacity + 1];
    currentSize=0;
}

/*  Insert  item  x  into  the  heap,  maintaining  heap  order.  Duplicates
are allowed. */
template <class eType>
bool Heap<eType>::insert( const eType & x )
{
    if( isFull( ) ) {
        cout << "insert - Heap is full." << endl;
        return 0;
    }
    // Percolate up
    int hole = ++currentSize;
    for(; hole > 1 && x < array[hole/2 ]; hole /= 2)
        array[ hole ] = array[ hole / 2 ];
    array[hole] = x;
}

template <class eType>
void Heap<eType>::deleteMin( eType & minItem )
{
    if( isEmpty( ) ) {
        cout << "heap is empty." << endl;
        return;
    }
    minItem = array[ 1 ];
    array[ 1 ] = array[ currentSize-- ];
    percolateDown( 1 );
}

We include the heap.h file before having the constructor of the heap. In the constructor, we are dynamically creating our array. We have added 1 to the capacity of the array as the first position of the array is not in use. We also initialize the currentSize to zero because initially Heap is empty.

Next we have the insert method. Inside the insert method, we will call the isFull() method. If the heap is full, we will display a message and return 0. If the heap is not full, we will insert the element in the heap and take a variable hole and assign it currentSize plus one value. Then we will have a ‘for loop’ which will be executed as long as hole is greater than 1. This is due to the fact that at position one, we have root of the array. Secondly, the element which we want to insert in the array is smaller than the array[hole/2]. In the loop, we will assign the array[hole/2] to array[hole]. Then we divide the hole by 2 and again check the loop condition. After exiting from the loop, we assign x to the array[hole]. Instead of performing multiple swaps which is expensive, we find the final position of the new node and then insert it at that position. The hole moves upward, and the parent is moved down until the final position is achieved.

The next method is deleteMin. First of all, it calls the isEmpty() method. If heap is empty, it will display a message and return. If the heap is not empty, it will delete the node. As the minimum value lies at the first position of the array, we save this value in minItem variable and store the currentSize at the first position of the array. At the same time, we reduce the currentSize by one as one element is being deleted. Then we call the percolateDown method, providing it the new root node. This method will make the tree a min-heap again.

🔑 Definition: template <class eType> : A C++ feature that allows the Heap class to work with any data type (e.g., integers, strings, objects) without rewriting the code for each type.

🔑 Definition: hole : A variable used in the insert method that represents the position in the array where the new element might be placed. It starts at the next available position and "percolates up" as parent values are moved down.

📌 Example: Insert value 3 into a min-heap [0, 5, 13, 12, 24] (currentSize=4).

1. Check if the heap is full. It is not.
2. hole = ++currentSize = 5.
3. Loop: hole > 1 (5 > 1) && x (3) < array[5/2] (array[2] = 13) → true.
   • array[5] = array[2] (13). hole = 5/2 = 2.
4. Loop: hole > 1 (2 > 1) && x (3) < array[2/2] (array[1] = 5) → true.
   • array[2] = array[1] (5). hole = 2/2 = 1.
5. Loop: hole > 1 is false. Exit loop.
6. array[1] = 3.
7. The final array is [0, 3, 5, 12, 24, 13], which is a valid min-heap.

⭐ Key Takeaways

The BuildHeap algorithm constructs a heap from an unordered array of N elements in O(N) time, which is significantly faster than inserting N elements one by one using O(N log N). The key to its efficiency is starting the percolateDown loop from the last internal node (N/2), because leaf nodes are already valid heaps. Other important heap operations, such as decreaseKey, increaseKey, and remove, are essential for implementing priority queues, where element priorities need dynamic adjustments. The C++ template implementation of the Heap class provides a reusable data structure, where insert uses "percolate up" to find the correct position for the new element and deleteMin removes the root and uses "percolate down" to restore the heap order. For the remove(p) method, a clever trick is to first decrease the node's value to negative infinity to make it the new root, then call deleteMin().

🧠 Quick Revision Questions

1. What is the time complexity of the BuildHeap algorithm compared to building a heap by calling insert() N times?
2. Explain why the for loop in the BuildHeap algorithm starts from i = N/2 instead of i = N.
3. In a min-heap, describe the steps to implement the decreaseKey(p, delta) operation, assuming the new value breaks the heap property.
4. How does the remove(p) method use decreaseKey and deleteMin to delete an arbitrary node from the heap?
5. In the C++ insert method, why is finding the final position of the new node using a "hole" more efficient than repeatedly swapping elements?

📘 Lecture 32 — Data Structures

📖 Overview: This lecture completes the implementation of the heap class by discussing the percolateDown, getMin, and buildHeap methods. It then provides a mathematical and visual proof that buildHeap runs in linear time, demonstrating its superiority over N log₂N algorithms.

🗂️ Topics Covered

This lecture covers the percolateDown method used in deleteMin and buildHeap operations, the getMin method for retrieving the minimum without deletion, the buildHeap method for constructing a heap from an unsorted array, and a detailed proof—both mathematical and non-mathematical—that buildHeap runs in linear time (O(N)). Small utility methods isEmpty, isFull, and getSize are also presented.

📝 Lecture Summary

perculateDown Method

This method takes an array index (called hole) as an argument and restores the heap order starting from that index downward. It stores the value at hole in a temporary variable tmp, then uses a for loop that continues as long as hole * 2 <= currentSize (i.e., the node has a left child). Inside the loop, the smaller of the two children is identified; if the left child is larger than the right child, child is incremented to point to the right child. If the smaller child's value is less than tmp, the child's value moves up to hole, and hole moves down to child. Otherwise, the loop breaks. Finally, tmp is placed in its correct position (array[hole]).

This method uses a single assignment inside the loop instead of three swap statements, making it more efficient. The "hole" (empty position) percolates downward until the correct location for tmp is found.

🔑 Definition — percolateDown: A method that restores the heap order by moving a value downward from a given index, comparing it with its children until the correct position is found. 📐 Formula: hole * 2 (left child), hole * 2 + 1 (right child) → used to find children of a node in an array-based heap. 📌 Example: In a min-heap, if the root (at index 1) is removed and the last element is moved to index 1, percolateDown(1) is called. If array[1] = 15, and its children are array[2] = 10 and array[3] = 12, the left child (10) is smaller. Since 10 < 15, the value 10 moves to index 1, and the hole moves to index 2. The process continues until 15 is placed correctly.

getMin Method

This method returns the minimum value in the heap (the root) without removing it, similar to the top method in a stack. It simply checks if the heap is not empty and returns array[1].

template <class eType>
const eType& Heap<eType>::getMin( )
{
    if( !isEmpty( ) )
        return array[ 1 ];
}

💡 Why this matters: Unlike deleteMin, getMin allows you to inspect the smallest element without altering the heap structure, which is useful for priority queue peek operations.

buildHeap Method

This method takes an external array anArray and its size n, copies it into the internal heap array (shifting from 0-based to 1-based indexing), sets currentSize = n, and then calls percolateDown(i) for every node from index currentSize / 2 down to 1. This bottom-up approach ensures all subtrees become valid heaps.

template <class eType>
void Heap<eType>::buildHeap(eType* anArray, int n )
{
    for(int i = 1; i <= n; i++)
        array[i] = anArray[i-1];
    currentSize = n;
    for( int i = currentSize / 2; i > 0; i-- )
        percolateDown( i );
}

The isEmpty, isFull, and getSize utility methods simply check or return currentSize and capacity values.

buildHeap in Linear Time

The buildHeap algorithm runs in linear time O(N), which is better than N log₂N. This is proven by showing that the sum of heights of all nodes (S) is a linear function of N. For a perfect binary tree of height h with N = 2^(h+1) – 1 nodes, the sum S = N – h – 1. For large N, the log term becomes insignificant, making S ≈ N. Since each percolateDown operation for a node at height h takes at most h steps, the total work is proportional to S, which is O(N).

Theorem

Statement: "For a perfect binary tree of height h containing 2^(h+1) – 1 nodes, the sum of the heights of nodes is 2^(h+1) – 1 – (h+1), or N – h – 1."

Mathematical Proof: In a perfect binary tree, there are 2ⁱ nodes at height h–i. The sum S = Σ 2ⁱ (h – i) for i = 0 to h–1. Multiplying by 2 and subtracting yields S = 2^(h+1) – 1 – (h+1) = N – (h+1). Since a complete tree has nodes between 2^h and 2^(h+1), S ≈ N – log₂(N+1). For large N, log₂(N+1) is insignificant, so S ≈ N.

Non-Mathematical (Visual) Proof: For each node of height h, darken h tree edges (first a left edge, then subsequent right edges). There are N – 1 total edges and h edges on the right path, so the number of darkened edges is N – 1 – h, which equals the sum of heights. In a 31-node perfect tree of height 4, there are 30 total edges, 4 unmarked (dotted) edges on the right path, and 26 marked edges—matching the sum of heights formula S = 31 – 4 – 1 = 26.

🔑 Definition — Sum of Heights (S): The total number of edges traversed if every node descends to its deepest leaf; it represents the upper bound on the number of value movements in buildHeap.

⭐ Key Takeaways

The percolateDown method is the core operation for maintaining heap order, used in both deleteMin and buildHeap. It avoids costly three-way swaps by using a single assignment per loop iteration. The buildHeap method constructs a heap from an unsorted array in linear time by calling percolateDown on all non-leaf nodes in reverse level order. The sum of heights of all nodes in a perfect binary tree equals N – h – 1, which is approximately N for large N, proving that buildHeap is O(N) rather than O(N log N). Utility methods like getMin, isEmpty, isFull, and getSize complete the heap class interface.

🧠 Quick Revision Questions

1. What is the termination condition of the for loop in percolateDown, and why does it use hole * 2 <= currentSize?
2. Explain why percolateDown uses a single assignment inside the loop instead of three swap statements.
3. In buildHeap, why does the loop start from currentSize / 2 and go down to 1?
4. Prove mathematically that buildHeap runs in linear time using the sum of heights theorem.
5. For a perfect binary tree with 31 nodes and height 4, how many edges are marked according to the visual proof, and what does this number represent?

📘 Lecture 33 — Priority Queue Using Heap, The Selection Problem, Heap Sort, Disjoint Set ADT, Equivalence Relations

📖 Overview: This lecture explores the implementation of a priority queue using a heap data structure, demonstrating how heaps improve efficiency over array-based implementations. It also introduces the selection problem, heap sort, and the Disjoint Set ADT with its applications in computer vision and equivalence relations.

🗂️ Topics Covered

The lecture covers implementing a priority queue using heap, including the PriorityQueue class with heap-based operations. It then discusses the selection problem for finding the kth smallest element, introduces heap sort as a sorting algorithm, and concludes with the Disjoint Set ADT, blob coloring in computer vision, and equivalence relations in mathematics.

📝 Lecture Summary

Priority Queue Using Heap

The lecture begins by implementing a priority queue using a heap instead of an array. The buildHeap method is preferred over insert when all data is available, as it takes less time than Nlog₂N. The code shows a PriorityQueue class that internally uses a heap of Event objects with a maximum size of 30 (PQMAX). The constructor creates a new Heap object, and the destructor deletes it. The remove() method calls deleteMin() on the heap, which returns the minimum element. The insert() method calls the heap's insert() method, which performs percolate up and down operations to place the new element at its correct position.

🔑 Definition — Heap: A complete binary tree where each node's key is either greater than or equal to (max-heap) or less than or equal to (min-heap) its children's keys.

The full() method calls isFull() on the heap, and length() calls getSize(). This implementation is more efficient than the array-based priority queue because the heap can readjust itself in log₂N time, compared to sorting the array after each insertion.

The Selection Problem

The selection problem involves finding the kth smallest (or largest) element from a list of N elements that can be totally ordered. For example, given 1000 numbers, finding the 10th smallest number.

One approach is to sort the array, taking Nlog₂N time. A faster approach uses the heap:

1. Put N elements into an array and apply the buildHeap algorithm
2. Perform k deleteMin operations
3. The last element extracted is the answer (the kth smallest)

🔑 Definition — Median: The value where half the numbers are greater and half are smaller. Mathematically, k = ⌈N/2⌉ for the median.

📐 Formula: buildHeap time complexity = O(N) (linear time) 📌 Example: To find the median of final marks (max 100) for N students, use buildHeap to construct a min-heap, then call deleteMin N/2 times. The N/2th marks extracted would be the median.

Heap Sort

If we call deleteMin N times (where k = N) and record the elements as they come off a min-heap, we get all elements sorted in ascending order. This is the basis of heapsort, a fast sorting algorithm that will be fine-tuned later in the course.

📐 Formula: Heap Sort time complexity = O(N log₂N) 📌 Example: For a min-heap of 100 elements, calling deleteMin 100 times and storing each removed element produces a sorted list in ascending order.

Disjoint Set ADT

The Disjoint Set ADT is used to handle relationships and answer queries like "Is Haaris related to Ahmad?" It works on the key property: If Haaris is related to Saad and Saad is related to Ahmad, then Haaris is related to Ahmad (transitivity).

🔑 Definition — Disjoint Set ADT: A data structure that maintains a collection of disjoint (non-overlapping) sets, supporting operations to find which set an element belongs to and to union two sets together.

Blob Coloring is a computer vision application where we partition pixels into disjoint sets (one set per blob). For a black and white image with five non-overlapping black blobs, the ADT creates one set per blob. This is also used in image segmentation problems, MRI scans, and CT scans.

Equivalence Relations

A binary relation R over a set S is called an equivalence relation if it has three properties:

1. Reflexivity: for all element x ∈ S, x R x
2. Symmetry: for all elements x and y, x R y if and only if y R x
3. Transitivity: for all elements x, y and z, if x R y and y R z then x R z

🔑 Definition — Equivalence Relation: A relation that is reflexive, symmetric, and transitive. The relation "is related to" over the set of people is an example of an equivalence relation.

💡 Why this matters: Understanding equivalence relations is fundamental to the Disjoint Set ADT implementation, as the relation "is in the same set" forms an equivalence relation.

⭐ Key Takeaways

The heap-based priority queue implementation is more efficient than the array-based version, with O(log₂N) readjustment time compared to O(N) sorting. The selection problem can be solved using buildHeap (O(N)) followed by k deleteMin operations, which is faster than sorting for small k. Heap sort emerges naturally from heap operations by extracting all elements. The Disjoint Set ADT is crucial for relationship tracking, computer vision (blob coloring, image segmentation), and medical imaging. Equivalence relations form the mathematical foundation for understanding how disjoint sets partition elements.

🧠 Quick Revision Questions

1. What is the time complexity advantage of using buildHeap instead of N insert operations when constructing a heap from N elements?
2. How would you find the 10th smallest element from 1000 numbers using a min-heap? What operations are required?
3. What happens if you call deleteMin N times on a min-heap and record all removed elements?
4. In the Disjoint Set ADT, what are the three properties of an equivalence relation, and how do they apply to the "is related to" relation?
5. How does blob coloring in computer vision relate to the Disjoint Set ADT? Give an example.

📘 Lecture 34 — Equivalence Relations and Disjoint Sets

📖 Overview: This lecture introduces the mathematical concept of equivalence relations and their connection to disjoint sets and equivalence classes. It lays the foundation for the dynamic equivalence problem, explaining how we can efficiently determine whether elements belong to the same set using union and find operations—a key data structure concept for solving real-world grouping problems.

🗂️ Topics Covered

The lecture covers equivalence relations with their three defining properties (reflexivity, symmetry, transitivity) and provides examples from family relationships and electrical circuits. It then discusses how equivalence relations partition sets into disjoint equivalence classes, introduces the dynamic equivalence problem, and presents the union/find operations as a solution. The lecture concludes by contrasting a naive matrix-based approach with a more efficient graph-based representation.

📝 Lecture Summary

Equivalence Relations

The lecture begins by defining equivalence relations mathematically. A binary relation R over a set S is called an equivalence relation if it satisfies three specific properties. The first property is reflexivity, meaning for all element x in S, x R x. The second is symmetry, meaning for all elements x and y, x R y if and only if y R x. The third is transitivity, meaning for all elements x, y and z, if x R y and y R z then x R z.

The lecture uses the example of family relationships to illustrate these properties. Haris, Saad, and Ahmed are used as examples: Haris and Saad are related as brothers, Saad and Ahmed are related as cousins. The relationship "is related to" satisfies reflexivity (everyone is related to themselves), symmetry (if Haris is Saad's brother, Saad is Haris's brother), and transitivity (if Haris is related to Saad and Saad to Ahmed, then Haris is related to Ahmed).

🔑 Definition — Equivalence Relation: A binary relation R over a set S that satisfies reflexivity (x R x for all x in S), symmetry (x R y if and only if y R x), and transitivity (if x R y and y R z, then x R z).

📌 Example: The relationship "≤" is NOT an equivalence relation. While it satisfies reflexivity (x ≤ x) and transitivity (if x ≤ y and y ≤ z, then x ≤ z), it fails symmetry since x ≤ y does not imply y ≤ x.

📌 Example: Electrical connectivity is an equivalence relation. If component a is connected to b by metal wire, then: a is connected to itself (reflexivity), if a is connected to b then b is connected to a (symmetry), and if a is connected to b and b is connected to c, then a is connected to c (transitivity).

💡 Why this matters: Understanding equivalence relations helps us mathematically model real-world grouping problems like family relationships, pixel connectivity in images, and circuit connectivity.

Disjoint Sets

An equivalence relation R over a set S can be viewed as a partitioning of S into disjoint sets. Each set of the partition is called an equivalence class of R, containing all elements that are related to each other.

🔑 Definition — Equivalence Class: A subset of S containing all elements that are related to each other through the equivalence relation R. Every member of S appears in exactly one equivalence class.

The lecture illustrates this with the analogy of grouping related people at a gathering. Initially, people are in separate groups, but when a marriage occurs between two groups, they merge into a larger family—mirroring the union operation on disjoint sets.

📌 Example: Given 1000 people, initially each person is in their own set. As family relationships are discovered, sets merge. To determine if person a is related to person b, we only need to check if they are in the same equivalence class.

Dynamic Equivalence Problem

The dynamic equivalence problem asks how to efficiently determine whether two elements belong to the same set given a set of binary relations. The lecture presents two approaches to solve this.

First approach: Store the relation as a two-dimensional boolean array. If we have n elements, we need an n×n matrix. For 1000 people, this requires 1,000,000 entries. For 1,000,000 people, it requires 10¹⁴ entries—prohibitively expensive in memory.

Second approach: Use a graph-based representation where:

• Each element is a node
• Each relation creates an edge between nodes
• Connected components represent equivalence classes

📌 Example: Given five elements {a1, a2, a3, a4, a5} with relations a1 R a2, a3 R a4, a5 R a1, and a4 R a2, we can determine that a3 R a5 even though this relation wasn't explicitly given—they are connected through the graph.

The lecture introduces two fundamental operations for this problem:

🔑 Definition — Find: Returns the name of the set (equivalence class) that contains a given element. Formally, Si = find(a).

🔑 Definition — Union: Merges two sets to create a new set. Formally, Sk = Si ∪ Sj.

Algorithm for adding a relation a R b:

1. Perform find(a) to get the set containing a
2. Perform find(b) to get the set containing b
3. If find(a) == find(b): a and b are already related (no action needed)
4. If find(a) != find(b): perform union(a, b) to merge the two sets

The lecture notes that all elements can be numbered sequentially from 1 to n, with initially Si = {i} for i = 1 through n. The name of the set returned by find is arbitrary—what matters is that find(x) = find(y) if and only if x and y are in the same set.

💡 Why this matters: For any sequence of at most m finds and up to n-1 unions, this algorithm will require time proportional to (m + n), making it highly efficient for large-scale problems.

⭐ Key Takeaways

Equivalence relations must satisfy reflexivity, symmetry, and transitivity—if any property is missing, the relation is not an equivalence relation. An equivalence relation partitions a set into disjoint equivalence classes where every element appears in exactly one class. The dynamic equivalence problem can be solved using the union/find algorithm: find determines which set an element belongs to, and union merges two sets. The naive matrix approach for determining relations is space-prohibitive for large datasets (O(n²) space), while the graph-based approach is more efficient. Elements can be numbered sequentially, and the find operation only needs to return consistent set identifiers to determine equivalence.

🧠 Quick Revision Questions

1. What are the three properties that a binary relation must satisfy to be an equivalence relation?
2. Why is the "≤" relation NOT an equivalence relation?
3. In the dynamic equivalence problem, what two operations are used to manage disjoint sets?
4. If we have 1000 people and want to use a boolean matrix to store all relations, how many entries would the matrix have?
5. When adding a new relation a R b, what must we check before performing a union operation?

📘 Lecture 35 — Dynamic Equivalence Problem

📖 Overview: This lecture explores the dynamic equivalence problem and its solution using disjoint set data structures. It explains how to efficiently implement the union and find operations using a parent array, with trees representing sets. Understanding these concepts is crucial for managing equivalence relations in various algorithms and data structures.

🗂️ Topics Covered

The lecture covers the dynamic equivalence problem, including the use of trees to represent sets and forests to represent collections of sets. It details the implementation of the parent array for storing set relationships, with examples of union and find operations. The discussion includes initialization of sets, performing unions to merge trees, executing finds to determine set membership, and analyzing the running time of these operations.

📝 Lecture Summary

Dynamic Equivalence Problem

The dynamic equivalence problem involves managing disjoint sets where elements are unique and belong to exactly one set. A tree is used to represent each set, with the root serving as the name of the set. The find operation returns the root (set name) for a given element, while the union operation merges two sets by making the root of one tree point to the root of another. A collection of trees is called a forest, and these trees are not necessarily binary—nodes may have more than two children. Initially, N elements form N separate trees, each with one node.

🔑 Definition — Forest: A collection of trees, used to represent multiple disjoint sets in this data structure.

Example 1

This example demonstrates union operations on eight elements (1 to 8). Initially, each element is in its own set. After union(5,6), set 6 becomes a child of set 5, making the new set named 5. Similarly, union(7,8) joins 8 as a child of 7. When union(5,7) is called, the set containing 7 (root 7) is merged into set 5, making 7 a child of 5. After union(3,4), set 4 becomes a child of 3. Finally, union(4,5) finds the root of 4 (which is 3) and merges set 5 into set 3, showing that union automatically finds the correct roots before merging.

💡 Why this matters: In the union operation, the caller does not need to provide the roots—the function automatically finds the set roots of the given elements before merging them.

Parent Array

The parent array stores the tree structure using a one-dimensional array. For each node i, Parent[i] contains the index of its parent, or -1 if it is the root. This approach uses array indices as pointers instead of actual memory addresses.

🔑 Definition — Parent Array: An array where each index represents an element, and the value at that index stores the parent of the element (or -1 for roots).

📐 Formula: Parent[i] = -1 if i is the root, otherwise Parent[i] = parent index.

Initialization

Initially, all elements are roots of their own sets. Using a for loop, each position in the parent array is set to -1.

📐 Formula: for (i = 0; i < n; i++) Parent[i] = -1 → This initializes all n elements as separate sets with no parents.

📌 Example: For 8 elements (1 to 8), the initialization results in: Parent[1]=-1, Parent[2]=-1, ..., Parent[8]=-1. All eight positions contain -1, representing eight separate trees with single nodes.

Find (i)

The find operation traverses from the given element i up to the root of its tree. It starts with j=i and follows parent pointers until reaching a node with parent value less than 0 (i.e., -1, the root).

📐 Formula: for(j=i; parent[j] >= 0; j=parent[j]) ; return j → This loop continues as long as parent[j] is not -1, moving j to its parent each iteration, eventually returning the root.

📌 Example: In the array after several unions, find(8) starts at position 8. Since Parent[8]=7, j becomes 7. Parent[7]=5, so j becomes 5. Parent[5]=3, so j becomes 3. Parent[3]=-1, so the loop ends, returning 3. Thus, 8 belongs to set 3.

Union (i, j)

The union operation merges two sets. It first finds the roots of both i and j using the find function. If the roots are different, it makes the root of j a child of the root of i by setting Parent[root_j] = root_i.

📐 Formula: root_i = find(i); root_j = find(j); if (root_i != root_j) parent[root_j] = root_i; → This merges the set containing j into the set containing i, with root_i becoming the new root.

📌 Example: After calling union(4,5), find(4) returns 3 (the root of 4's set), and find(5) returns 5 (itself a root). Since 3 ≠ 5, Parent[5] is set to 3. Now the tree has root 3 with children 4 and 5, and 5 has children 6, 7, and 8 in its subtree.

Example 2

This example traces the same union operations using the parent array representation. After all unions, the array shows: Parent[1]=-1, Parent[2]=-1, Parent[3]=-1, Parent[4]=3, Parent[5]=3, Parent[6]=5, Parent[7]=5, Parent[8]=7. The number of -1 values (four: positions 1, 2, 3, and none at 4,5,6,7,8) indicates four trees in the forest.

📌 Example: To verify find(6) in this array: Start at 6, Parent[6]=5 → j=5. Parent[5]=3 → j=3. Parent[3]=-1, return 3. So 6 belongs to set 3.

Running Time Analysis

The parent array implementation is more space-efficient than a Boolean matrix. For N elements, a Boolean matrix requires N² locations, while the parent array needs only N locations. The union operation is a constant time operation (O(1)) once roots are found. The running time of find(i) is proportional to the height of the tree containing node i, which can be O(N) in the worst case. The goal is to modify union to ensure that tree heights stay small.

💡 Why this matters: The parent array approach uses significantly less space than a two-dimensional matrix while still efficiently handling equivalence relations. However, tree height can degrade performance, motivating improvements like union by size or rank.

⭐ Key Takeaways

The dynamic equivalence problem is solved using trees to represent sets, with a forest representing all sets and the root serving as the set name. The parent array provides an efficient one-dimensional storage structure using array indices as pointers, with -1 indicating roots. Union is a constant-time operation once roots are found, while find's running time depends on tree height and can be O(N) in the worst case. The number of trees in the forest can be determined by counting the number of -1 values in the parent array. The key trade-off is between the simplicity of this array-based approach and the potential for performance degradation due to tree height, motivating future improvements.

🧠 Quick Revision Questions

1. In the parent array representation, what does the value -1 at position i indicate?
2. After performing union(5,6) followed by union(5,7), what would be the parent of 7 in the array?
3. What is the running time complexity of the find operation in the worst case, and what factor determines it?
4. How many trees exist in a forest represented by a parent array with the following values: [-1, -1, -1, 3, 5, 5, 7]?
5. In the union function implementation, why is it necessary to first call find on both arguments before merging the sets?

📘 Lecture 36 — Running Time Analysis, Union by Size, Union by Height, Sprucing up Find, Timing with Optimization

📖 Overview: This lecture focuses on optimizing the disjoint set (union-find) data structure. It introduces union by size and union by height to keep trees shallow, and path compression in find to flatten the tree for faster future lookups. The goal is to achieve nearly linear time performance for a sequence of union and find operations.

🗂️ Topics Covered

The lecture covers the running time analysis of union and find operations on up-trees. It then introduces union by size (weight) to maintain shallow trees, analyzes its depth guarantee (O(log n)), and presents union by height as an alternative. The key optimization of path compression in the find operation is explained in detail with figures, and the overall timing with all optimizations is stated via a theorem involving the inverse Ackermann function.

📝 Lecture Summary

Running Time Analysis

In the previous lecture, disjoint sets and up-trees implemented via arrays were discussed. While union is a constant-time operation, the running time of find(i) is proportional to the height of the tree containing node i. In the worst case, this height can be n (e.g., performing unions on a sorted list: union(1,2), union(2,3), etc., creates a tree of height n). The goal is to modify union to keep heights small, ensuring find operations are fast. Balancing techniques from binary search trees are not suitable here due to array implementation complexity, so a simpler method called Union by Size is used.

Union by Size

This method maintains the size (number of nodes) of every tree. During a union, the smaller tree is made a subtree of the larger one. In the implementation, for each root node i, instead of setting parent[i] to -1, we set it to -k if the tree rooted at i has k nodes. This allows the find loop's terminating condition (checking for a negative value) to still work correctly.

🔑 Definition — Union by Size (or Union by Weight): A strategy for merging two disjoint sets where the root of the tree with fewer nodes is made a child of the root of the tree with more nodes. 💡 Why this matters: This ensures the tree's height does not grow as quickly, directly improving the performance of find.

📐 Algorithm for union(i, j) based on size:

root1 = find(i);
root2 = find(j);
if (root1 != root2)
    if (parent[root1] <= parent[root2]) // root1 has more or equal nodes (more negative)
        parent[root1] += parent[root2]; // update size
        parent[root2] = root1;          // attach smaller tree
    else                                // root2 has more nodes
        parent[root2] += parent[root1]; // update size
        parent[root1] = root2;          // attach smaller tree

📌 Example: Consider an array of 8 elements, all initially -1 (singleton trees). union(4,6): Both trees have size 1. The condition parent[4] <= parent[6] is true (both are -1). The tree with root 4 absorbs node 6. parent[4] becomes -2 (size 2), and parent[6] becomes 4. union(1,4): The tree with root 1 has size 1 (-1), and tree with root 4 has size 2 (-2). Since root4's tree is larger (-2 <= -1), node 1 becomes a child of node 4. The new tree at root 4 has size 3 (-3). This process maintains a tree of height 2.

Analysis of Union by Size

If unions are done by weight (size), the depth of any element is never greater than log₂ n.

• Intuitive Proof: An element’s depth only increases when it is in the smaller tree during a union. In such a union, the resulting tree is at least twice as large as the element's previous tree. Since the tree’s size doubles each time the element’s depth increases, the depth can increase at most log₂ n times before the tree contains all n elements. This is a significant improvement from a worst-case depth of n.

Union by Height

This is an alternative to union-by-size. The strategy maintains the height of each tree. During a union, the tree with a smaller height is made a subtree of the one with a larger height. The implementation details are left as an exercise, but the concept is very similar to union-by-size and is essentially equivalent in terms of performance.

Sprucing up Find

This optimization focuses on the find operation using path compression. During find(i), as we traverse the path from node i to the root, we update the parent entry of every node on that path to directly point to the root.

🔑 Definition — Path Compression: A technique used in the find operation that flattens the tree by making every node on the path from a node to the root become a direct child of the root.

📐 Algorithm for find(i) with path compression (recursive):

find(i) {
    if (parent[i] < 0)  // i is the root
        return i;
    else
        return parent[i] = find(parent[i]); // compress path
}

📌 Example: In a deep tree, calling find(1) traverses nodes 1 -> 2 -> 9 -> 4 -> 13 -> 7 (root). The recursive call reaches the root (7) and then returns. As the recursion unwinds, the call find(13) sets parent[13] = 7, find(4) sets parent[4] = 7, find(9) sets parent[9] = 7, and so on. After this single find, nodes 1, 2, 4, 9, and 13 all have their parent set directly to the root (7). This drastically reduces the height of the tree for future find operations on any of these nodes.

💡 Why this matters: This is a "pay now, reap the benefits later" optimization. A single find operation may do more work, but subsequent find operations on compressed paths become nearly constant time.

Timing with Optimization

Theorem: A sequence of m union and find operations, n of which are find operations, can be performed on a disjoint-set forest with union by rank (weight or height) and path compression in worst-case time proportional to (m * α(n)), where α(n) is the inverse Ackermann function. For all practical purposes, α(n) ≤ 4, which means the average time per operation is essentially constant. The union-find structure is therefore extremely efficient for a sequence of m operations, achieving nearly linear time in m.

⭐ Key Takeaways

1. To improve find performance in up-trees, we must keep tree heights small by optimizing the union operation.
2. Union by Size/Weight and Union by Height are simple strategies that guarantee the depth of any node is at most O(log n), a huge improvement from the potential O(n) worst case.
3. Path compression in the find operation further flattens the tree, making subsequent finds significantly faster by directly connecting nodes on the traversal path to the root.
4. By combining union by rank (size or height) with path compression, a sequence of m union and find operations runs in essentially O(m) time (linear), making it one of the most efficient data structures for maintaining disjoint sets.
5. The inverse Ackermann function confirms the incredible efficiency of the union-find algorithm, which is practical for real-world applications requiring many set operations.

🧠 Quick Revision Questions

1. What is the goal of "union by size/weight" and how does it achieve this?
2. In union by size, what value is stored in the parent array of a root node, and why is it negative?
3. What is the maximum possible depth of any node after performing unions strictly by size, and why?
4. Explain how the path compression technique in the find operation changes the structure of a tree.
5. What is the approximate worst-case running time (in terms of m and n) for a sequence of m union and find operations using union by rank and path compression, and what function makes it so efficient?

📘 Lecture 37 — Image Segmentation and Maze Example

📖 Overview: This lecture explores practical applications of disjoint sets and the union/find algorithm. It demonstrates how these data structures can efficiently segment digital images based on pixel intensity thresholds and generate random mazes by systematically removing walls between cells until a path exists from entrance to exit.

🗂️ Topics Covered

The lecture begins with a review of union/find optimization techniques, including union by size and path compression. It then introduces image segmentation as a key application, explaining how pixel intensities are thresholded to create binary images and how union/find groups connected regions. The maze generation problem is presented next, where cells are initially isolated by walls and randomly merged using union operations until the entrance and exit cells belong to the same set. A pseudo code algorithm for maze generation is provided, followed by step-by-step pictorial illustrations of the process.

📝 Lecture Summary

Review

The lecture reviews union and find methods with special reference to optimization. Union by size or union by weight reduces tree size, while path optimization in the find method further reduces tree traversal. The time required by the find/union algorithm is proportional to m+n when there are m unions and n finds. Union is a constant time operation that links two trees, whereas find involves tree traversal. Disjoint sets increase as the forest decreases.

Image Segmentation

Image segmentation divides an image into different parts based on pixel intensity. An image is a collection of pixels, each with a value representing intensity (e.g., 0 for black, 255 for white). Pixels can be grouped using a threshold value—for example, replacing all pixel values ≥ 4 with 1 and values < 4 with 0 to create a binary image. The lecture demonstrates this with a 5×5 grid of pixel values (0, 2, 4) representing different gray levels.

🔑 Definition — Threshold: A cutoff value used to classify pixels into two groups (e.g., above or below the threshold). 📌 Example: Given a 5×5 matrix with values 0, 2, and 4, applying threshold = 4 replaces all 4s with 1 and all other values with 0, producing a binary matrix. Using the union/find algorithm, we group adjacent 1s into disjoint sets to identify connected regions in the image.

The union/find algorithm processes each row of the matrix. Initially, there are 25 individual sets (one per pixel). When two adjacent pixels both have value 1, a union operation combines their sets. This process continues across all rows, eventually forming disjoint sets of connected 1s. For example, in the first row, two 1s at columns 3 and 4 are unioned; in the second row, 1s at columns 2 and 3 are unioned with the set above, merging into a set of four 1s. Continuing this process yields two disjoint sets of 1s—one large set on the right side and a smaller set on the left.

When the threshold is changed to 2, more pixels become 1s, and the union operation merges them into a single large blob of connected 1s.

💡 Why this matters: The union/find algorithm segments images quickly without requiring extra memory—all processing occurs in a single array representing the up-tree.

Maze Example

A maze is a puzzle where a user enters from one side and finds a path to the exit, with many paths leading to dead ends. Maze generation can be done using the disjoint sets algorithm.

🔑 Definition — Equivalence relation: Two cells are equivalent if they can be reached from each other (walls removed so there is a path from one to the other).

Consider a 5×5 grid with 25 cells numbered 0 to 24. Each cell is isolated by walls from others. The entrance is cell 0 and the exit is cell 24. The algorithm randomly removes walls until the entrance and exit cells are in the same set. Removal of a wall is equivalent to a union operation. A randomly chosen wall is not removed if the cells it separates are already in the same set.

📌 Example: Initially, there are 25 sets, each containing one cell. Randomly choose cell 11 and its right wall, merging cell 11 and cell 12 into one set {11,12}. Then choose cell 6 and its bottom wall, merging cell 6 with the set containing 11 and 12 to form {6,11,12}. Continue this process—when cell 8 and its top wall (cell 3) are chosen and are in different sets, they are merged into set {3,8}. This continues until cells 0 and 24 eventually belong to the same set, indicating a path exists from entrance to exit.

Pseudo Code of the Maze Generation

The pseudo code for the MakeMaze function takes a size parameter and generates a maze of that size.

MakeMaze(int size) {
    entrance = 0; 
    exit = size-1;
    while (find(entrance) != find(exit)) {
        cell1 = randomly chosen cell
        cell2 = randomly chosen adjacent cell
        if (find(cell1) != find(cell2)) {
            knock down wall between cells
            union(cell1, cell2)
        }
    }
}

The while loop continues until the find operations on entrance and exit return the same set. Inside the loop, two adjacent cells are randomly chosen. If they are in different sets, the wall between them is removed and union is applied to combine them into one set.

📌 Example: In the 5×5 grid, the loop might first choose cell 11 and cell 12 (adjacent horizontally). Since find(11) and find(12) return different sets initially, the wall is removed and union is performed. Later, cell 6 and cell 11 might be chosen; if they are in different sets, the wall is removed and they merge. The loop stops when cell 0 and cell 24 are in the same set.

⭐ Key Takeaways

The union/find algorithm efficiently segments images by grouping adjacent pixels with similar intensity values using thresholding, requiring no extra memory beyond the up-tree array. Maze generation becomes straightforward using the same algorithm: randomly remove walls between cells, applying union operations until the entrance and exit cells belong to the same set. The algorithm is simple—a while loop checks if entrance and exit are in the same set, and if not, randomly selects adjacent cells to union if they are in different sets. This demonstrates the power of disjoint sets for solving real-world problems involving connectivity and equivalence relations.

🧠 Quick Revision Questions

1. How does the union/find algorithm segment a binary image into connected regions?
2. In maze generation, what condition causes the while loop to terminate?
3. Why should a wall not be removed if the two cells it separates are already in the same set?
4. What is the role of the threshold value in image segmentation, and how does changing it affect the result?
5. How many sets initially exist in a 5×5 maze generation problem, and what happens to this number as walls are removed?

📘 Lecture 38 — Tables and Dictionaries

📖 Overview: This lecture introduces the Table Abstract Data Type (ADT) and Dictionaries, fundamental data structures for organizing information in rows and columns. It covers the core operations on tables and their implementations using unsorted and sorted sequential arrays, culminating in the binary search algorithm for efficient data retrieval. Understanding these concepts is crucial for database systems, compiler design, and any application requiring organized data storage and retrieval.

🗂️ Topics Covered

The lecture begins by defining Tables and Dictionaries as abstract data types consisting of rows (records) and columns (fields), with a key field uniquely identifying each record. It then details the three primary operations on the Table ADT: insert, find, and remove. Two implementations are discussed: the unsorted sequential array, where insertion is fast but searching is slow, and the sorted sequential array, where searching becomes fast using binary search but insertion requires data shifting. The lecture concludes with a detailed explanation of the binary search algorithm and its efficiency in O(log n) time.

📝 Lecture Summary

Tables and Dictionaries

A table, as an abstract data type, is a collection of rows and columns of information. Unlike a simple two-dimensional array, a table can have columns of different data types (e.g., integer, string). Each column is known as a field, and each row is called a record or tuple. For example, a telephone directory has three fields: name, address, and phone number. Another example is a bank account table with fields like account number, account title, account type, and balance. Tables are widely used in databases for applications like payroll software, and in compilers where symbol tables store information about program variables, including their name, type, and scope.

The key is a special field used to uniquely identify an entry in a table. In databases, this is known as the primary key. Only the key value is needed to find, insert, or delete a specific record. For example, in a telephone directory, the name field serves as the key, and searching for "Imran Ahmad" returns the complete record containing the address and phone number.

🔑 Definition — Key: A field in a table that uniquely identifies a record (entry), ensuring that no two records have the same key value.

💡 Why this matters: The concept of a key is foundational for efficient data retrieval in databases and data structures, as it allows operations to target specific records without scanning the entire table.

Operations on Table ADT

insert This method is used to add a new record to the table. It requires both the key and the entry (the complete record data). The insert operation places the key and its associated fields into the table.

find This method searches for an entry in the table given a key value. It locates the complete record that matches the provided key. For example, in an employees table where employee id is the key, providing id 15466 returns the entire employee record.

remove This method is given a key value to find and delete the associated entry from the table.

Implementation of Table

The choice of implementation for the Table ADT depends on several factors:

• How often entries are inserted, found, and removed
• How many key values are likely to be used
• The likely pattern of searching for keys
• Whether the table fits in memory
• How long the table will exist

In a table, it is best practice to store the key and the entry (complete record) separately, even though the key's value may be part of the entry. A TableNode represents a single row and contains both the key and entry components.

🔑 Definition — TableNode: The structural element of a table that holds both the key and the entry (complete record) for a single row.

Unsorted Sequential Array

In this implementation, TableNodes are stored consecutively in an array in any order. Each element of the array contains both a key and an entry. For practical implementation, a class (e.g., Employee or PhoneDirectoryEntry) can be created to represent each record type, and an array of objects is used to store them.

• insert: Fast — data is added at the back of the array, requiring O(1) time.
• find: Slow — must search through keys one at a time, potentially checking all n entries. Time is proportional to n.
• remove: Slow — must first perform a find (O(n)), then remove the entry. Time is proportional to n.

💡 Why this matters: The unsorted sequential array provides fast insertion but slow searching and deletion, making it suitable for applications where data is frequently added but rarely searched or removed.

Sorted Sequential Array

This implementation keeps data in the array in sorted order based on the key field. For example, in a telephone directory, names are stored alphabetically. When a new entry is inserted, the array must be re-sorted or elements shifted to maintain the sorted order.

• insert: Slow — requires shifting existing entries to find the correct sorted position. Time is proportional to n.
• find: Fast — uses binary search, requiring O(log n) time.
• remove: Slow — first finds the entry in O(log n) time, then shifts remaining elements to maintain sorted order. Time is proportional to n.

Binary Search

Binary search is a searching algorithm that works on sorted data, finding an element in O(log n) time. If there are 100,000 elements, binary search requires at most 20 steps (since log₂(100,000) ≈ 17).

The algorithm works like looking up a word in a dictionary:

1. Start from the middle of the sorted array.
2. If the target word comes before the middle word, search in the first half.
3. If the target word comes after, search in the second half.
4. Repeat the process on the remaining half until the target is found or the search space is empty.

With each step, the search space is halved, making the algorithm extremely efficient compared to linear search.

🔑 Definition — Binary search: A search algorithm that repeatedly divides a sorted array in half to find a target value, achieving O(log n) time complexity.

📐 Formula: Time complexity of binary search → O(log₂ n), where n is the number of elements in the sorted array.

📌 Example: Searching for "Salman Akhtar" in a sorted telephone directory with 100,000 entries. Start at entry 50,000; if "Salman Akhtar" alphabetically comes before, search the first half (entries 1-50,000). Continue halving until the target is found. Maximum steps required = 17 (since 2¹⁷ = 131,072 > 100,000).

⭐ Key Takeaways

The Table ADT is a fundamental data structure consisting of records (rows) and fields (columns), where a unique key field is used for all operations including insert, find, and remove. Two primary implementations exist: unsorted sequential arrays (fast insertion, slow search in O(n)) and sorted sequential arrays (slow insertion due to shifting, but fast search using binary search in O(log n)). Binary search is a critical algorithm that repeatedly halves the search space, making it exponentially faster than linear search for large datasets. The choice between implementations depends on the expected frequency of operations—whether insertion or searching is more common in the specific application.

🧠 Quick Revision Questions

1. What is the difference between a two-dimensional array and a table (Table ADT)?
2. What is a key in a table, and why must it be unique?
3. How does the insertion time complexity differ between unsorted and sorted sequential array implementations of a table?
4. Explain the binary search algorithm and why its time complexity is O(log n).
5. In what real-world applications would you prefer an unsorted sequential array over a sorted sequential array for table implementation?

📘 Lecture 39 — Searching an Array: Binary Search and Skip Lists

📖 Overview: This lecture covers binary search algorithm for sorted arrays, its implementation in C++, and its efficiency analysis. It then introduces alternative implementations of the Table ADT using linked lists and the novel skip list data structure that overcomes limitations of previous approaches through hierarchical chains.

🗂️ Topics Covered

The lecture explores binary search algorithm with three detailed examples demonstrating different search scenarios, followed by its C++ implementation and efficiency analysis showing O(log₂N) performance. It then examines linked list implementation of Table ADT and introduces the skip list data structure as a more efficient alternative, including its representation, higher-level chains, and formal definition.

📝 Lecture Summary

Searching an Array: Binary Search

Binary search is an efficient algorithm for finding an item in a sorted array by repeatedly dividing the search interval in half. The algorithm compares the target value to the middle element of the array; if they are equal, the search is complete. If the target value is less than the middle element, the search continues in the left half; otherwise, it proceeds in the right half. This process is independent of data type and works for both numeric and string data.

The algorithm in pseudocode:

if (value == middle element)
    value is found
else if (value < middle element)
    search left half of list with the same method
else
    search right half of list with the same method

Binary Search – Example 1

Case 1: val == a[mid] — The target value equals the middle element.

Given array a with indices 0 to 8 containing sorted values: 1, 5, 7, 9, 10, 13, 17, 19, 27.

🔑 Value (val): The item being searched for in the array.

📐 Formula: mid = (low + high) / 2

📌 Example: Searching for val = 10

• low = 0, high = 8
• mid = (0 + 8) / 2 = 4
• a[mid] = 10, which equals val = 10
• Result: Found immediately at position 4

Binary Search – Example 2

Case 2: val > a[mid] — The target value is greater than the middle element.

📌 Example: Searching for val = 19

• low = 0, high = 8, mid = (0 + 8) / 2 = 4
• a[mid] = 10, val (19) > a[mid] (10)
• Since array is sorted, the left half cannot contain 19
• New low = mid + 1 = 5, high remains 8
• Search continues in the right half (positions 5 to 8)

Binary Search – Example 3

Case 3: val < a[mid] — The target value is less than the middle element.

📌 Example: Searching for val = 7

• low = 0, high = 8, mid = (0 + 8) / 2 = 4
• a[mid] = 10, val (7) < a[mid] (10)
• New high = mid - 1 = 3, low remains 0
• Now searching in left half (positions 0 to 3)

Step 2 in left half:

• low = 0, high = 3, mid = (0 + 3) / 2 = 1
• a[mid] = 5, val (7) > a[mid] (5)
• New low = mid + 1 = 2, high remains 3

Step 3:

• low = 2, high = 3, mid = (2 + 3) / 2 = 2
• a[mid] = 7, val (7) = a[mid] (7)
• Found at position 2 after three comparisons

💡 Why this matters: Without binary search, finding value 27 would require 9 comparisons sequentially, but with binary search it requires only 3 comparisons. The efficiency gain increases dramatically with larger arrays.

Binary Search – C++ Code

The function isPresent implements binary search for an integer array.

🔑 isPresent function: A C++ function that performs binary search on a sorted array and returns 1 if the value is found, 0 otherwise.

int isPresent(int *arr, int val, int N)
{
    int low = 0;
    int high = N - 1;
    int mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (arr[mid] == val)
            return 1; // found!
        else if (arr[mid] < val)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return 0; // not found
}

The function receives an array pointer arr, the value to search val, and array size N. It initializes low=0 and high=N-1. The while loop continues as long as low <= high. Inside the loop, mid is calculated, and comparisons determine whether to search the left or right half. Returns 1 if found, 0 if not found after loop termination.

Important: This function requires the data to be sorted to work properly; otherwise it will fail.

Binary Search – Binary Tree

Binary search can be visualized as a binary tree structure. The search process divides a list into two smaller sub-lists until a sub-list is no longer divisible. This corresponds to a fully balanced binary tree where each node represents a decision point, and left/right subtrees represent the two halves.

Binary Search - Efficiency

The efficiency of binary search is analyzed by counting the number of bisections needed.

📐 Formula: i = log₂N

This shows that after a maximum of log₂N bisections, either the item is found or determined to be absent.

Comparison of Array Implementation:

• Insert: Must find sorted position and shift elements — O(N) worst case
• Remove: Proportional to N — O(N)
• Search: Maximum log₂N comparisons — O(log₂N)

💡 Why this matters: Keeping data sorted for binary search pays off during search operations, making search extremely efficient at the cost of slightly more expensive insertions and deletions.

Implementation 3 (of Table ADT): Linked List

Linked list implementation of the Table ADT stores nodes that may be scattered in memory (not contiguous like arrays).

• TableNodes are stored consecutively (unsorted or sorted)
• insert: Add to front requires O(1) for unsorted; O(n) for sorted list to find correct position
• find: Search through potentially all keys one at a time — O(n) for both unsorted and sorted
• remove: Find the element, then remove using pointer alterations — O(n)

The fixed size of arrays becomes a constraint, while linked lists have no such limitation. However, the find operation using linked lists becomes slower because binary search works only for arrays (since linked list nodes are not contiguous in memory).

Implementation 4 (of Table ADT): Skip List

Skip list is a data structure introduced by Professor Bill Pugh in 1990 to overcome basic limitations of previous lists.

Key characteristics:

• Overcomes limitations where search and update require linear time
• Provides fast searching of sorted chain
• Offers alternative to BST and related tree structures (where balancing can be expensive)
• Relatively recent data structure

Skip List - Representation

A skip list consists of head and tail special nodes at the start and end of the list respectively. The key innovation is adding additional pointers to speed up search.

Using a pointer to the middle element, we can perform binary search-like operations. For example, to find 60 in a sorted skip list, we first compare with the middle element (40), determine that 60 is greater, then search the right half — similar to binary search in arrays.

Skip List - Higher Level Chains

• Level 0 chain includes all elements (the original linked list)
• Level 1 chain includes every other element
• Level 2 chain includes every fourth element
• Level i chain includes every 2ⁱ-th element

The skip list becomes a hierarchy of chains where level i contains a subset of elements in level i-1. Using this structure, elements can be found in O(log₂n) time.

However, the frequency of pointers becomes so high compared to data size that management becomes difficult. Insert and remove operations become complex because single insertion or removal requires adjusting many pointers.

Professor Pugh suggested that instead of leveling in powers of 2, it should be done randomly, which makes the skip list easier to manage.

Skip List - Formally

A skip list for a set S of distinct (key, element) items is a series of lists S₀, S₁, ..., Sₕ such that:

• Each list Sᵢ contains the special keys +∞ and -∞
• List S₀ contains the keys of S in non-decreasing order
• Each list is a subsequence of the previous one: S₀ ⊇ S₁ ⊇ ... ⊇ Sₕ
• List Sₕ contains only the two special keys

💡 Why this matters: The idea of randomness in skip lists is new and will be explored in the next lecture to understand how it makes the skip list data structure easy and useful.

⭐ Key Takeaways

Binary search is a powerful O(log₂N) algorithm that works only on sorted arrays by repeatedly dividing the search space in half. The C++ implementation uses three variables (low, high, mid) and a while loop to efficiently locate elements. While linked lists offer flexibility without size constraints, they cannot support binary search because their nodes are not contiguous in memory. The skip list data structure overcomes this limitation by adding hierarchical chains of pointers, achieving O(log₂n) search time similar to binary search trees. Randomness in skip lists makes insertions and deletions practical by eliminating the complexity of maintaining exact power-of-two leveling.

🧠 Quick Revision Questions

1. What is the formula to calculate the middle position in binary search, and why must the array be sorted for this algorithm to work?
2. In binary search, after how many bisections will you be left with exactly one item from an array of N elements?
3. Why can't binary search be applied to linked lists, and what is the time complexity of search in a linked list implementation of Table ADT?
4. What are the four components of the formal definition of a skip list, and what special keys does each list contain?
5. What was Professor Bill Pugh's key insight about level distribution in skip lists, and how does it address the complexity of insert and remove operations?

📘 Lecture 40 — Skip List

📖 Overview: This lecture introduces the skip list data structure, a probabilistic alternative to balanced trees that enables efficient search (O(log n)) on linked lists. By using multiple levels of additional pointers, skip lists provide binary-search-like performance without the complexity of rotations or array-based limitations. The lecture covers the structure, search algorithm, randomized insertion, and deletion from skip lists.

🗂️ Topics Covered

The lecture covers the definition and structure of skip lists as a series of sorted linked lists with special keys, the search algorithm that moves across and down through levels, randomized insertion using coin tossing to determine node height, and deletion by finding and removing nodes from all levels they occupy. The key insight is that skip lists achieve logarithmic performance through probabilistic balancing without requiring rotations.

📝 Lecture Summary

Skip List

A skip list for a set S of distinct (key, element) items is a series of lists S₀, S₁, ..., Sₕ such that:

• Each list Sᵢ contains the special keys +∞ and -∞
• List S₀ contains the keys of S in non-decreasing order
• Each list is a subsequence of the previous one, i.e., S₀ ⊇ S₁ ⊇ ... ⊇ Sₕ
• List Sₕ contains only the two special keys

In a skip list, nodes exist only once but have multiple forward pointers to higher levels. For example, node 23 may have one pointer to node 26 in S₀ and another pointer to node 31 in S₁. The levels are created randomly, not by taking every 2nd or 4th node like in a perfect skip list.

🔑 Definition — Skip List: A linked list with multiple levels of additional pointers where each level is a subsequence of the level below, allowing binary-search-like traversal.

📌 Example: In a skip list with nodes 12, 23, 26, 31, 34, 56, 64, 78 in S₀, only nodes 23, 31, 34, 64 appear in S₁, only node 31 appears in S₂, and S₃ contains only -∞ and +∞.

💡 Why this matters: Unlike arrays, skip lists don't require contiguous memory or shifting elements during insertion/deletion, while still providing O(log n) search time.

Skip List Search

The search algorithm for a key x follows these rules: • Start at the first position of the top list • At current position p, compare x with y ← key(after(p)) • x = y: return element(after(p)) • x > y: "scan forward" (move to next node in same list) • x < y: "drop down" (move to the level below at the same position) • If we try to drop down past the bottom list, return NO_SUCH_KEY

📌 Example: Searching for 78 in the skip list:

1. Start at S₃'s first node (-∞), next is +∞ > 78 → drop down to S₂
2. In S₂, next is 31 < 78 → scan forward to +∞ > 78 → drop down to S₁
3. In S₁, next is 34 < 78 → scan forward to 64 < 78 → scan forward to +∞ > 78 → drop down to S₀
4. In S₀, next after 64 is 78 → found!

This requires far fewer steps than traversing S₀ linearly through 12, 23, 26, 31, 34, 56, 64 to reach 78. The search time is O(log n), similar to binary search trees.

Insertion in Skip List

Insertion uses a randomized algorithm with coin tossing:

Step 1: Repeatedly toss a coin until we get tails, and denote with i the number of times the coin came up heads.

Step 2: If i > h (current height), add new lists Sₕ₊₁, ..., Sᵢ₊₁, each containing only the two special keys.

Step 3: Search for x and find positions p₀, p₁, ..., pᵢ of items with largest key less than x in each list S₀, S₁, ..., Sᵢ.

Step 4: For j ← 0, ..., i, insert item (x, o) into list Sⱼ after position pⱼ.

🔑 Definition — Randomized Algorithm: An algorithm that performs coin tosses (uses random bits) to control its execution. Its running time depends on the outcome of the coin tosses.

📐 Formula: Coin toss logic:

b ← random()
if b <= 0.5  // head: increment i, continue tossing
else          // tail: stop tossing

📌 Example: Inserting 15 into a skip list containing 10, 23, 36:

1. Coin toss results: i = 2 (two heads before tail)
2. Current h = 2, so no new lists needed
3. Search: start from S₂ top, drop to S₁ (next is 23 > 15), drop to S₀
4. In S₀: scan past 10 (10 < 15), stop before 23 (23 > 15)
5. Insert 15 after 10 in S₀, S₁, and S₂ (positions p₀, p₁, p₂)

The new node appears in S₀ always, plus in as many higher levels as the coin toss determined (i levels).

💡 Why this matters: The random height ensures the skip list remains probabilistically balanced without needing complex rebalancing operations like AVL rotations.

Deletion from Skip List

To remove an item with key x from a skip list: • Search for x and find positions p₀, p₁, ..., pᵢ of items with key x, where pⱼ is in list Sⱼ • Remove positions p₀, p₁, ..., pᵢ from lists S₀, S₁, ..., Sᵢ • Remove any empty lists except the one containing only the two special keys

📌 Example: Removing node 34 from skip list:

1. Search from top list: drop from S₃ to S₂ where 34 is found (p₂)
2. Continue to S₁ where 34 is found (p₁)
3. Continue to S₀ where 34 is found (p₀)
4. Remove 34 from S₂, S₁, and S₀
5. Since S₂ now contains only -∞ and +∞ (like S₃), keep only one top list

Unlike insertion, deletion involves no randomness or coin tossing — only pointer manipulation.

⭐ Key Takeaways

A skip list is a multi-level linked list structure that achieves O(log n) search time through probabilistic balancing, making it a practical alternative to balanced trees without requiring rotations or array-based storage. The search algorithm combines horizontal scanning with vertical dropping, moving from the topmost sparse list down to the densest bottom list until the target is found or determined absent. Insertion uses a randomized coin-tossing process to determine how many levels a new node should occupy, ensuring the data structure remains probabilistically balanced without deterministic rebalancing. Deletion is straightforward: find the node in all levels it occupies, remove it, and clean up any now-empty top levels. Unlike AVL trees, skip lists trade deterministic guarantees for simpler implementation while still providing expected logarithmic performance.

🧠 Quick Revision Questions

1. What are the four properties that define a skip list's structure, and what special keys appear in every list?
2. In the skip list search algorithm, when do you "scan forward" versus "drop down," and what happens if you need to drop past the bottom list?
3. How does the randomized insertion algorithm determine how many levels a new node should occupy, and what step involves coin tossing?
4. In the insertion example with value 15, why was the node inserted into S₂ even though S₂ already had only -∞ and +∞?
5. How does deletion from a skip list differ from insertion in terms of randomness, and what cleanup step is needed after removing a node that was the only non-special node in a level?

📘 Lecture 41 — Data Structures Lecture No. 41

📖 Overview: This lecture reviews skip list implementation using TowerNode and QuadNode structures, then analyzes skip list performance. It introduces AVL trees as balanced binary search trees and transitions into hashing as a method to achieve constant-time operations for find, insert, and remove. The lecture concludes with examples of hash functions and their implementation.

🗂️ Topics Covered

The lecture covers review of skip list structure and implementation using TowerNode with dynamic arrays of next pointers, the QuadNode approach with four pointers and node copying, performance analysis of skip lists showing expected space proportional to n and search/insert/delete proportional to log n, introduction to AVL trees as balanced BSTs, the concept of hashing as a methodology for constant-time table operations, and examples of hash functions including ASCII summation and base-b conversion.

📝 Lecture Summary

Review

In the previous lecture, three methods of skip list were studied: insert, find, and remove. The skip list has nodes at 0th, 1st, and 2nd levels containing actual values like 12, 23, 34, and 45. Node 34 appears in three nodes. Implementation requires a structure with next pointers. For example, data values 20, 26, 30, 40, 50, 57, 60 are stored at different levels, with nodes like 26 and 57 having two next pointers while node 40 has three next pointers.

🔑 Definition — TowerNode: A node in a skip list that contains an array of next pointers, with the actual number of pointers decided by a random procedure.

🔑 Definition — MAXLEVEL: An upper limit on the number of levels (and thus next pointers) in a node, imposed to prevent memory allocation problems from excessive coin-flip heads.

📌 Example: When inserting data and heads appear six times, six next pointers are needed. The TowerNode factory allocates space for six next pointers dynamically. Each pointer points to nodes at their own level — for node 40, its 0-level pointer points to node 50, its 2nd pointer points to node 57, and its third pointer points to tail.

Quad Node

Another method for skip list implementation uses the QuadNode structure, which does not use an array of pointers but instead contains four next pointers.

🔑 Definition — QuadNode: A node that stores item, link to node before, link to node after, link to node below, and link to node above.

📌 Example: In a QuadNode structure, values 23, 34, and 64 are copied two times, and value 31 is copied three times. The bottom layer has nil down pointers, the top layer has nil up pointers, and rightmost column has nil right pointers. This creates a doubly skip list with backward movement capability.

💡 Why this matters: QuadNode avoids dynamic array allocation — every list node contains four fixed pointers, and the QuadNode factory returns a node with these four pointers that must be linked up, bottom, left, and right.

Performance of Skip Lists

The analysis is probability-based. In a skip list with n items, the expected space used is proportional to n. For n items, we need n memory locations for data plus approximately 2n memory locations for next pointers. The proportionality constant is around 15 to 20, but it cannot be n² or n³.

The expected search, insertion, and deletion time is proportional to log n. This resembles binary search tree performance. With 100,000 nodes, log n is about 20, so approximately 20 steps are needed for any operation.

🔑 Definition — log n performance: For n items, the number of steps required for search, insert, or delete operations grows logarithmically with n.

💡 Why this matters: Skip list implementation is simple (similar to linked lists) and provides balanced-tree performance without explicit balancing algorithms.

AVL Tree

Insertion, deletion, and searches are performed based on key values. Each node contains key and data together (like telephone directory with name as key and address/number as entry). The AVL tree ensures the tree remains balanced and does not become degenerated.

🔑 Definition — AVL Tree: A balanced binary search tree where the find, insert, and remove operations are all proportional to log n.

📌 Example: In an AVL tree, search is on the key (e.g., person's name) while the entry contains address, telephone number, and remaining information. Being balanced, it maintains log n performance for all operations.

Hashing

Hashing is not a new data structure but an algorithmic procedure and methodology for using existing data structures. It aims to make find, insert, and remove operations constant time — a single step operation.

🔑 Definition — Hash function: A mathematical function that takes a key (like a name or roll number) and returns an array index as an integer number.

The process: Key → Hash Function → Array Index. Data is stored in an array (static or dynamic), but not in consecutive locations. The storage place is calculated using the key and hash function.

📌 Example: To insert employee data with name as key, pass the name to hash function to get an integer, then use that integer as array index to insert the data. For find, pass key to hash function, obtain array index, and retrieve data from that position. If data is not present at that array position, it means data is not found. For remove, pass key to hash function, get array index, and set that position to null.

💡 Why this matters: All three operations (insert, find, remove) become constant time operations, requiring only one step each, unlike tree or list structures requiring traversal.

Examples of Hashing

Using fruit names as keys, the hash function hashCode returns specific integer values:

hashCode("apple") = 5 hashCode("watermelon") = 3 hashCode("grapes") = 8 hashCode("cantaloupe") = 7 hashCode("kiwi") = 0 hashCode("strawberry") = 9 hashCode("mango") = 6 hashCode("banana") = 2

The resulting array (size 10): index 0 = kiwi, index 1 = empty, index 2 = banana, index 3 = watermelon, index 4 = empty, index 5 = apple, index 6 = mango, index 7 = cantaloupe, index 8 = grapes, index 9 = strawberry.

This creates an associative array where users can think of table["apple"], table["watermelon"], etc., while internally integer indices are used via hashCode.

🔑 Definition — Associative array: An array where keys (like strings) are used as indices instead of numbers, implemented internally using hash functions.

For string keys, one hash function implementation adds ASCII values of characters:

h(str) = (sum of str[i] for i=0 to length-1) % TableSize

📐 Formula: h(str) = (∑ str[i]) % TableSize → Add all character ASCII values, then take modulo with table size.

📌 Example: h("ABC") = (65 + 66 + 67) % 55 = 198 % 55 = 33

C++ implementation of hashCode:

int hashCode(char* s) {
    int i, sum = 0;
    for(i = 0; i < strlen(s); i++)
        sum = sum + s[i]; // ASCII value
    return sum % TABLESIZE;
}

Another possibility converts string into some number in arbitrary base b (b might be a prime number):

h(str) = (∑ str[i] × b^i) % T

📐 Formula: h(str) = (∑ str[i] × b^i) % TableSize → Multiply each character's ASCII value by base raised to position power, sum, then take modulo.

📌 Example: h("ABC") with b=7 and T=55 = (65 × 7⁰ + 66 × 7¹ + 67 × 7²) % 55 = (65 + 462 + 3283) % 55 = 3810 % 55 = 45

If keys are integers, key % T is generally a good hash function unless data has undesirable features.

📌 Example: If T=10 and all keys end in zero, then key%T = 0 for all keys. With employee IDs ending in zero, all would hash to index 0, making the hash function useless. Therefore, T should be a prime number to avoid such situations.

⭐ Key Takeaways

Skip lists can be implemented using either TowerNode (with dynamic array of next pointers) or QuadNode (with four fixed pointers: up, down, left, right). Skip lists provide expected search, insert, and delete time proportional to log n with space proportional to n, making them efficient and simple to implement. Hashing is a methodology rather than a data structure, designed to achieve constant-time operations for find, insert, and remove by using a hash function to compute storage locations. The hash function must return an integer index from a key, and common implementations include summing ASCII values or using a base conversion formula. For integer keys, key % table size is effective when the table size is a prime number to avoid undesirable patterns.

🧠 Quick Revision Questions

1. What are the two different node structures discussed for implementing skip lists, and what are their key differences?
2. What is the expected time complexity for search, insert, and remove operations in a skip list?
3. How does hashing achieve constant-time operations for find, insert, and remove?
4. What problem occurs if table size is 10 and all keys end in zero, and how should table size be chosen?
5. Write the formula for converting a string to a hash value using base b, and compute h("ABC") with b=7 and T=55.

📘 Lecture 42 — Collision & Linear Probing

📖 Overview: This lecture addresses the fundamental problem of collision in hashing — when two different keys produce the same hash index. It introduces three collision resolution strategies, with detailed focus on linear probing, including its implementation for insert, find, and delete operations, and the clustering problem that arises. Understanding collision resolution is critical for implementing efficient hash tables in real-world applications.

🗂️ Topics Covered

The lecture begins by discussing hash functions for integer keys and the importance of using prime table sizes to avoid systematic collisions. It formally defines collision and presents three primary solutions: searching for an empty location (linear probing), using multiple hash functions, and using linked lists at each array position. The bulk of the lecture then details linear probing, including how insertion, lookup, and deletion work with wrap-around, the need for three cell states (occupied, empty, deleted), and the clustering problem that degrades performance. Quadratic probing is briefly introduced as an improvement.

📝 Lecture Summary

Hash Function for Integer Keys & Prime Table Size

If keys are integers, a good hash function is key % T where T is the table size. However, if T=10 and all keys end in 0, then key % 10 = 0 for all keys — a catastrophic collision scenario. To avoid such problems, T should be a prime number. When storing 100 records, choose a prime number near 100 as MAXTABLESIZE. Using a prime number helps resolve problems where keys share common factors with the table size, though it cannot guarantee unique hash values for all keys.

🔑 Definition — hash function for integers: key % T where T should be a prime number to minimize systematic collisions.

📐 Formula: hash(key) = key % TableSize → takes the remainder when the key is divided by the table size to produce an array index.

📌 Example: If T=10 and all employee IDs end in 0 (e.g., 100, 200, 300), then hash(100) = 0, hash(200) = 0, hash(300) = 0 — all keys map to index 0. Using a prime T like 11 would give different values: 100 % 11 = 1, 200 % 11 = 2, 300 % 11 = 3.

Collision

Collision occurs when two or more keys (data items) produce the same hash index. This is inevitable and not the hash function's fault — the hash function is a mathematical formula that takes keys and returns a number. The caller (our ADT implementation) is responsible for handling collisions using a collision resolution strategy. The fundamental principle is "first come, first served" — the first value that hashes to a location gets it; subsequent values must be handled differently.

🔑 Definition — collision: When two values hash to the same array location.

📌 Example: In a fruit table, hash("mango") = 6 and mango is stored at position 6. When inserting hash("honeydew") = 6, a collision occurs because position 6 is already occupied. The resolver must find another location for honeydew.

Three collision resolution solutions are presented:

Solution #1: Search for an empty location — Stop searching when we find the value or an empty location. Search must wrap-around at the end.

Solution #2: Use a second hash function — Then a third, fourth, fifth, etc. Call these hash functions one by one until an empty location is found.

Solution #3: Use the array location as the header of a linked list — The array becomes an array of pointers to TableNode. Each list node stores the data. When collision occurs, insert the new node at the front of the list at that position.

💡 Why this matters: Collision resolution is not optional — it is guaranteed to happen with real-world data. Choosing the right strategy affects both time efficiency and memory usage.

Linear Probing

Linear probing is the first solution (open addressing/closed hashing). When a collision occurs, the array is scanned sequentially (with wrap-around) in search of an empty cell. More formally, cells at h₀(x), h₁(x), h₂(x), ... are tried in succession where:

hi(x) = (hash(x) + f(i)) mod TableSize, with f(0) = 0

For linear probing, f(i) = i (a linear function), so: location(x) = (hash(x) + i) mod TableSize

🔑 Definition — linear probing: A collision resolution strategy that scans the array sequentially (with wrap-around) in search of an empty cell by adding 1, 2, 3, etc. to the original hash value.

📐 Formula: location(x) = (hash(x) + i) mod TableSize where i starts at 0 and increments by 1 each time a collision occurs.

📌 Example — Insertion with collisions: Given a partial array with birds:

• Position 142: robin
• Position 143: sparrow
• Position 144: hawk
• Position 145: empty
• Position 147: bluejay
• Position 148: owl

Inserting "seagull" where hashCode("seagull") = 143:

1. Check position 143: occupied by sparrow (not empty, not equal to seagull)
2. Add 1 → position 144: occupied by hawk (not empty, not equal)
3. Add 2 → position 145: empty → store seagull here (2 collisions resolved)

📌 Example — Find operation: To find "hawk" where hashCode("hawk") = 143:

1. Check position 143: occupied by sparrow (not hawk)
2. Add 1 → position 144: occupied by hawk → found (1 probe after initial check)

📌 Example — Wrap-around: To insert "cardinal" where hashCode("cardinal") = 147 and position 147 is occupied by bluejay, position 148 is occupied by owl, and 148 is the last position:

1. Check 147: occupied by bluejay
2. Add 1 → position 148: occupied by owl
3. Wrap around to position 0: check, then 1, 2, etc. until empty space found

Three states for deletion: When using linear probing, deletion creates a "hole" problem. If an element in the middle of a chain is deleted, the probe may incorrectly stop at the empty cell and conclude the target item is not in the table. Solution: maintain three states for each cell:

• Occupied: has valid data
• Empty (never used): no data has ever been stored here
• Deleted (previously used): had data that has been removed

Clustering problem: Linear probing tends to form clusters — groups of items not containing any open slots. The bigger a cluster gets, the more likely new values will hash into it, making it even bigger. Clusters cause efficiency to degrade from O(1) to near O(n).

📌 Example of clustering: With three consecutive collisions at positions 143, 144, and 145 (sparrow, hawk, seagull), the next item hashing to 143 would be placed at 146, extending the cluster further. This behaves almost like sequential array storage instead of scattered hashing.

Quadratic probing is introduced as a solution to clustering:

• Use F(i) = i² (square of i) to resolve collisions
• If hash function resolves to H and cell H is occupied, try H+1², H+2², H+3², ...

📐 Formula: location(x) = (hash(x) + i²) mod TableSize

📌 Example: Inserting seagull with quadratic probing:

• hash("seagull") = 143, position 143 occupied
• Add 1² → position 144: occupied
• Add 2² → position 147: if available, store here (data now scattered instead of clustered)

Linked list approach comparison:

• Advantages over open addressing: simpler insertion and removal, array size is not a limitation
• Disadvantage: memory overhead is large if entries are small

The array becomes an array of pointers, and each position has a linked list. When collision occurs, the new item is inserted at the front of the linked list at that position.

⭐ Key Takeaways

Collision is inevitable in hashing and must be handled by the ADT implementation, not the hash function. Linear probing is the simplest approach — it scans sequentially for empty cells using (hash(x) + i) mod TableSize — but suffers from clustering, which degrades performance from O(1) toward O(n). To handle deletions correctly, cells must have three states (occupied, empty, deleted) so that probe chains are not broken. Quadratic probing (using i² instead of i) helps scatter data to reduce clustering, while linked list chaining eliminates the array-full problem at the cost of memory overhead. The fundamental trade-off is between simplicity and efficiency — no single collision resolution strategy is perfect for all scenarios.

🧠 Quick Revision Questions

1. Why should table size be a prime number when using the key % T hash function for integer keys?
2. What is the formula for linear probing and how does wrap-around work when probing reaches the end of the array?
3. Explain the clustering problem in linear probing — why does it occur and how does it affect performance?
4. Why are three cell states (occupied, empty, deleted) needed for deletion in linear probing? What would happen with only two states?
5. How does quadratic probing differ from linear probing, and what advantage does it offer over linear probing?

📘 Lecture 43 — Data Structures

📖 Overview: This lecture concludes the discussion of hashing with animations of collision resolution strategies and explores practical applications where hashing is suitable or unsuitable. It then introduces the topic of sorting, beginning with elementary algorithms like selection sort, which serve as baseline for comparing more efficient sorting methods.

🗂️ Topics Covered

The lecture covers hashing animation demonstrating linear probing, quadratic probing, and linked list chaining in a Java applet. It then discusses practical applications of hashing including compiler symbol tables, spell checkers, game programming, and inequality checking. The lecture examines when hashing is suitable versus when other data structures like AVL trees are better. Finally, it introduces sorting concepts and elementary sorting algorithms, focusing on selection sort.

📝 Lecture Summary

Hashing Animation

In the previous lecture, we discussed collision strategies in hashing including Linear Probing, Quadratic Probing, and Linked List chaining. Hashing is a vast research field covering hash functions, storage, and collision issues. Using hashing, operations of insert, delete, and find are performed in constant time, meaning the time does not increase with data volume. However, when collisions occur, the time does not remain constant. With linear probing, data must be inserted by sorting the array sequentially. With quadratic probing, a similar sequential approach is used. With linked list chaining, constructing linked lists takes time and memory.

The lecture demonstrates these three strategies using animations in a Java applet. The applet shows an array of size 100 with indices from 0 to 99. Each array element has two locations, so 200 elements can be stored. When the first collision occurs, the program uses the 2nd part of the array location. When a 2nd collision occurs, data is stored using the chosen collision resolution method.

The hash function used is x mod 100, meaning when a number is passed to it, it takes mod with 100 and returns the result used as the array index. The program generates 100 random numbers and stores them using the hash function.

🔑 Definition — Hashing: A technique that maps data of arbitrary size to fixed-size values (hash values) using a hash function, enabling constant-time operations for insert, delete, and find.

📐 Formula: hash value = key mod tableSize → The remainder when dividing the key by the table size determines the array index for storing or retrieving data.

📌 Example: Number 506 is divided by 100, remainder is 6, so it is stored at array location 6. Number 206 also has remainder 6, so it is stored in the 2nd part of location 6. Number 806 has remainder 6 but both parts of location 6 are occupied, so using linear probing it is stored at location 7. Number 807 has remainder 7, but location 7 is already occupied due to linear probing, so it is stored at location 8. This demonstrates a clustering effect where numbers with remainder 63 cluster around location 63.

For quadratic probing, the array size is 75 and each location stores two numbers. In quadratic probing, we add the square of 1 (1), then square of 2 (4), then square of 3 (9), and so on in case of collisions. The hash function uses mod with 75.

For linked list chaining, the hash function uses 50 to take mod with numbers. When both parts of a location are filled, a linked list appears attached to that location. For example, four numbers have remainder 0 — two are stored in the array and the next two are stored using the link list attached at location 0.

The lecture notes that hashing is not covered in great depth here as it belongs to algorithms and analysis of algorithms domain, which is not part of this course.

Applications of Hashing

Compilers use hash tables to keep track of declared variables (symbol table). A symbol table is an important part of the compilation process. The compiler puts variables inside the symbol table during compilation, keeping track of different attributes including variable name, type, scope, and function name where declared. Operations on the symbol table include insertion of variable information, search for variable information, or deletion of a variable. Insert and find are the most commonly used operations. A variable name serves as the parameter (or key) to these operations. However, if a variable named x exists outside a code block and another variable with the same name and type is declared inside that block, scope becomes the differentiating factor. Assuming all variables have unique names, the variable name can be used as the key. The compiler inserts variable information by calling the insert function and retrieves variable values by passing the variable name.

A hash table can be used for on-line spelling checkers — if misspelling detection (rather than correction) is important, an entire dictionary can be hashed and words checked in constant time. To find spelling mistakes, first take all words from the dictionary and construct a hash table. To check a text, take each word and compare it with all words in the hash table. If a word is not found, there is a high probability it is incorrect, though there is a low probability the word is correct but absent from the dictionary. Based on this high probability, a message can be displayed to the user.

Game playing programs use hash tables to store seen positions, thereby saving computation time if the position is encountered again. Consider chess where positions of pieces (64 pieces) can be used as the key to store in the hash table. If the program wants to analyze whether a player has encountered a similar situation before, it passes the positions to the find function. When the positions are hashed again, the previously present index is returned, indicating the situation was encountered before.

Hash functions can be used to quickly check for inequality — if two elements hash to different values, they must be different. Sometimes you only need to know if values are equal or not, not which is smaller or larger. If two data items don't collide, their hash values will be different, indicating the values are unequal.

💡 Why this matters: Hashing enables constant-time operations for many real-world applications, making it invaluable for compiler design, spell checking, game AI, and equality testing — but understanding its limitations is equally important for choosing the right data structure.

When Hashing is Suitable?

Hash tables are very good if there is a need for many searches in a reasonably stable table. The dictionary hash table example demonstrates this — the hash table was constructed once and lookup operations were frequent while insertions occurred very rarely.

Hash tables are not so good if there are many insertions and deletions, or if table traversals are needed — in this case, AVL trees are better. In applications requiring frequent reading and writing of data, hash tables might not be a good solution. However, there are no hard and fast statistics — you must be a good software engineer to choose the relevant data structure.

Hashing is very slow for any operations which require the entries to be sorted, for example finding the minimum key. Data is inserted into the hash table array without any sort order and is scattered through the array with holes. The animation showed no real sequence of filling — some clusters formed due to collisions but there was no order. Hashing is not useful in these circumstances.

The important thing is how one data structure can be implemented in six different ways. As long as the interface remains the same, different internal implementations do not matter from the client perspective.

Sorting

Sorting means to put data in a certain order or sequence. Sorting has been discussed scattered through topics in this course but not as a separate topic. When traversing a binary search tree in in-order, the obtained data happens to be sorted. With min-heap, if elements are removed one by one, data is obtained in sorted order.

Sorting is so useful that in 80-90% of computer applications, sorting appears in one form or another. Normally, sorting and searching go together. Extensive research has been done on sorting, and very efficient algorithms have been developed. Vast mathematical analysis has been performed on these algorithms.

🔑 Definition — Sorting: The process of arranging data in a specific order (typically ascending or descending) based on some comparison criteria.

📌 Example: Given array [20, 8, 5, 10, 7], sorting in ascending order produces [5, 7, 8, 10, 20]. The minimum number becomes the first element and the largest element becomes the last element.

Elementary Sorting Algorithms

The elementary sorting algorithms include Selection Sort, Insertion Sort, and Bubble Sort. These are called elementary because they are very simple and act as baseline algorithms for comparison with more efficient algorithms.

Selection Sort

Main idea:

• Find the smallest element
• Put it in the first position
• Find the next smallest element
• Put it in the second position
• Continue until you get to the end of the list

This technique searches the whole array and finds the smallest number. The smallest number is put on the first position while the previous element in this position is moved somewhere else. Then find the second smallest number and put it in the second position, again shifting the previous number. This activity is repeated until the array is sorted. This technique is called selection sort because we select elements for their sorted positions.

💡 Why this matters: Selection sort provides a simple, intuitive approach to sorting that helps understand the fundamental concept of sorting algorithms before moving to more efficient methods.

⭐ Key Takeaways

Hashing provides constant-time operations (insert, delete, find) but performance degrades with collisions. The three collision resolution strategies — linear probing, quadratic probing, and linked list chaining — each have different tradeoffs in time and memory usage. Hashing is most suitable for applications with many searches in stable tables (like compiler symbol tables and spell checkers) but is not suitable when many insertions/deletions are needed, table traversals are required, or sorted order is important. Sorting is fundamental to computer science, appearing in 80-90% of applications, and elementary algorithms like selection sort provide baseline understanding for studying more efficient sorting methods.

🧠 Quick Revision Questions

1. What are the three collision resolution strategies demonstrated in the hashing animation, and how does each handle a collision when both parts of an array location are filled?

2. Why is hashing considered suitable for compiler symbol tables and spell checkers but unsuitable for operations requiring sorted output?

3. In selection sort, what is the main idea, and how does it arrange elements in ascending order step by step?

4. What is the hash function used in the linear probing animation, and how does it determine the array index for a given number?

5. When would AVL trees be a better choice than hash tables, and why?

📘 Lecture 44 — Data Structures Lecture No. 44

📖 Overview: This lecture continues the discussion of sorting algorithms, covering three elementary sorting methods: selection sort, insertion sort, and bubble sort. It explains their algorithms, code implementations, and time complexity analysis, concluding by introducing the concept of N log₂(N) algorithms as more efficient alternatives.

🗂️ Topics Covered

This lecture covers three elementary sorting algorithms—selection sort, insertion sort, and bubble sort—with detailed explanations, C++ code, and analysis of their O(N²) time complexity. It also introduces the concept of N log₂(N) algorithms, including merge sort, quick sort, and heap sort, and compares their performance with the elementary sorts.

📝 Lecture Summary

Selection Sort

The main idea of selection sort is to repeatedly find the smallest element in the array and put it in its correct position. First, find the smallest element and swap it with the element in the first position. Then find the next smallest in the remaining elements and put it in the second position, continuing until the entire array is sorted.

🔑 Definition — Selection Sort: An algorithm that repeatedly finds the smallest element from the unsorted portion and moves it to the beginning.

📐 Formula: Total searches = 1 + 2 + 3 + ... + N = N(N+1)/2 ≈ O(N²) → The total number of comparisons grows proportionally to N².

📌 Example: Sorting array [19, 5, 7, 12] in ascending order:

• Step 1: Find smallest (5), swap with 19 → [5, 19, 7, 12]
• Step 2: Find smallest in remaining [19, 7, 12] (7), swap with 19 → [5, 7, 19, 12]
• Step 3: Find smallest in remaining [19, 12] (12), swap with 19 → [5, 7, 12, 19]

The findIndexMin function searches from a given start position to find the minimum element's index. The selectionSort function uses this to find the position, then swaps the minimum element with the current count position. This algorithm is an in-place sorting algorithm as it requires no additional storage.

💡 Why this matters: Selection sort is simple but inefficient for large datasets because its time grows with N².

Insertion Sort

The main idea of insertion sort is to build a sorted portion of the array on the left by inserting each new element into its proper position. Start by considering the first two elements and swapping if out of order. Then consider the third element and insert it into the proper position among the first three, and continue until all elements are processed.

🔑 Definition — Insertion Sort: An algorithm that sorts by repeatedly taking the next element and inserting it into its correct position within the already sorted portion of the array.

📐 Formula: Total shifts = (2 + N)(N-1)/2 = O(N²) → The worst-case number of shifts grows proportionally to N².

📌 Example: Sorting array [19, 12, 5, 7]:

• Step 1: Take first two (19,12), 12 < 19, swap → [12, 19, 5, 7]
• Step 2: Take third element (5), shift 12 and 19 right, insert 5 at position 0 → [5, 12, 19, 7]
• Step 3: Take fourth element (7), shift 12 and 19 right, insert 7 between 5 and 12 → [5, 7, 12, 19]

The insertionSort function uses a variable val to hold the current element, then shifts larger sorted elements to the right to create space. When the inner loop exits, the value is inserted at arr[pos+1]. This shifting is the additional overhead that makes this algorithm O(N²).

💡 Why this matters: Insertion sort is efficient for small or nearly sorted datasets but poor for large unsorted arrays.

Bubble Sort

The main idea of bubble sort is to exchange neighboring items repeatedly until the largest item reaches the end of the array, then repeat for the remaining elements. Smaller elements "bubble up" to the top while larger elements sink to the bottom.

🔑 Definition — Bubble Sort: An algorithm that repeatedly steps through the array, comparing adjacent elements and swapping them if they are in the wrong order.

📐 Formula: Total iterations = 1 + 2 + 3 + ... + N = N(N+1)/2 = O(N²) → The number of comparisons grows proportionally to N².

📌 Example: Sorting array [19, 12, 5, 7]:

• Pass 1: Compare (19,5) → swap → [5,19,12,7]; (19,12) → swap → [5,12,19,7]; (19,7) → swap → [5,12,7,19]
• Pass 2: Compare (5,12) → no swap; (12,7) → swap → [5,7,12,19]
• Pass 3: Compare (5,7) → no swap; array sorted

The bubbleSort function uses a swapped variable to track whether any swap occurred in a pass. The bound variable limits the inner loop to the unsorted portion. If no swap occurs in a pass, the while loop exits as the array is sorted.

💡 Why this matters: Bubble sort can detect a sorted array early, but in the worst case, it is still O(N²).

Summary

All three elementary algorithms—selection sort, insertion sort, and bubble sort—are in place algorithms with time complexity proportional to N². They are easy to understand and code but expensive for large datasets. The following table compares N² and N log₂(N) for different values of N:

N log₂(N) Algorithms

N log₂(N) algorithms are significantly more efficient than N² algorithms. These include merge sort, quick sort, and heap sort, which all fall under the divide and conquer category. The divide and conquer strategy splits the problem into smaller parts, solves each part separately, and then combines the results.

📌 Example of divide and conquer sorting:

• Unsorted array: [10, 12, 8, 4, 2, 11, 7, 5]
• Split into two parts: [10, 12, 8, 4] and [2, 11, 7, 5]
• Sort each part separately: [4, 8, 10, 12] and [2, 5, 7, 11]
• Merge the two sorted parts: [2, 4, 5, 7, 8, 10, 11, 12]

💡 Why this matters: For large datasets, N log₂(N) algorithms can be thousands of times faster than N² algorithms.

⭐ Key Takeaways

The three elementary sorting algorithms—selection sort, insertion sort, and bubble sort—are all in-place algorithms with O(N²) time complexity, making them simple but inefficient for large datasets. The key differences are in their approach: selection sort finds the minimum and swaps, insertion sort builds a sorted portion by inserting each element, and bubble sort swaps adjacent pairs to bubble larger values to the end. For the exam, remember the N² formulas for each algorithm and understand that N log₂(N) algorithms like merge sort, quick sort, and heap sort are far superior for large datasets, as shown by the comparison table where N=1,000,000 yields N²=10¹² versus N log₂(N)≈20 million.

🧠 Quick Revision Questions

1. What is the time complexity of selection sort, and what formula represents the total number of searches?
2. In insertion sort, what is the main overhead that contributes to its O(N²) time complexity?
3. How does bubble sort determine when the array is completely sorted?
4. Why are N log₂(N) algorithms considered better than N² algorithms for large datasets?
5. What is the divide and conquer strategy, and which sorting algorithms use it?

📘 Lecture 45 — Divide and Conquer, Mergesort, Quicksort, and Course Overview

📖 Overview: This lecture covers the divide and conquer strategy applied to sorting algorithms, focusing on mergesort and quicksort. It explains how these algorithms achieve O(n log₂ n) time complexity compared to O(n²) of elementary sorts, and concludes with a comprehensive overview of the entire data structures course.

🗂️ Topics Covered

The lecture introduces divide and conquer as a strategy to improve sorting efficiency, demonstrating how splitting a list into halves reduces time from n² to approximately (n/2)²+(n/2)²+n. It covers the mergesort algorithm in detail including its recursive implementation, the mergeArrays procedure, and analysis showing O(n log₂ n) time but O(n) extra space. Quicksort is introduced as a divide and conquer algorithm that uses partitioning around a pivot value. The lecture concludes with a course overview covering arrays, linked lists, stacks, queues, trees, AVL trees, threaded binary trees, union/find, table ADTs, skip lists, and hashing.

📝 Lecture Summary

Divide and Conquer

The divide and conquer strategy splits a list into two parts, sorts each part separately, and then merges them into a single sorted array. This approach significantly reduces sorting time compared to elementary algorithms.

For n=100, elementary sorting takes approximately n² = 10000 time units. Using divide and conquer with insertion sort: (100/2)² + (100/2)² + 100 = 2500 + 2500 + 100 = 5100 — roughly half the time.

The subdivision can continue recursively: halves into quarters, quarters into eighths, until reaching single elements (n=1). This mirrors binary search where we subdivide an array until finding the target or reaching individual elements.

💡 Why this matters: The divide and conquer strategy fundamentally improves sorting from O(n²) to O(n log₂ n), making it practical for large datasets.

Mergesort

Mergesort is a divide and conquer algorithm that:

• Splits the list in half
• Mergesorts the two halves recursively
• Merges the two sorted halves together

The algorithm involves three steps:

1. If the number of items to sort is 0 or 1, return
2. Recursively sort the first and second halves separately
3. Merge the two sorted halves into a sorted group

🔑 Definition — Mergesort: A recursive sorting algorithm that divides the list in half, sorts each half recursively, then merges the sorted halves.

mergeArrays

The mergeArrays function merges two sorted arrays into a single sorted temporary array. It uses three indexes: i for the first array, j for the second array, and k for the temporary array. At each step, the smaller of the two current elements is placed into the temporary array, and the corresponding index (i or j) is incremented along with k. When one array is exhausted, remaining elements from the other array are copied directly.

📐 Process: Compare a[i] and b[j], place the smaller into tmp[k], increment k and the appropriate index (i or j). Continue until one array is exhausted, then copy remaining elements.

📌 Example: Given arrays a = [3,5,15,28,30] and b = [6,10,14,22,43,50]:

• Compare 3 and 6 → place 3 in tmp
• Compare 5 and 6 → place 5 in tmp
• Compare 15 and 6 → place 6 in tmp
• Compare 15 and 10 → place 10 in tmp
• Continue until a is exhausted, then copy remaining b elements
• Result: tmp = [3,5,6,10,14,15,22,28,30,43,50]

Mergesort and Linked Lists

Mergesort also works with linked lists. The list is divided into two halves (knowing the size), each half is sorted recursively, and the sorted halves are merged together.

Mergesort Analysis

• Mergesort is O(n log₂ n) time
• Merging two lists of size n/2 takes O(n) time
• There are log₂ n levels of merging
• Mergesort is not an in-place sorting algorithm — it requires O(n) extra space for the temporary array
• This extra space requirement is a disadvantage compared to insertion sort and selection sort which are in-place

Quicksort

Quicksort is another divide and conquer algorithm based on partitioning the list around a pivot value. It is both O(n log₂ n) and in-place (no extra array needed).

The process:

1. Select a pivot element (e.g., the middle element)
2. Swap it with the last element
3. Use two indexes: low (starting from left, searching for element greater than pivot) and high (starting from right, searching for element less than pivot)
4. Swap the elements at low and high when both stop
5. Continue until low and high cross
6. Swap the pivot element with the element at the crossing position
7. Recursively quicksort the left part and right part

📌 Example: Array = [4,12,10,8,5,2,11,7,3], pivot = 5

• Swap pivot 5 with last element 3 → [4,12,10,8,3,2,11,7,5]
• low finds 12 (>5), high finds 2 (<5), swap → [4,2,10,8,3,12,11,7,5]
• low finds 10 (>5), high finds 3 (<5), swap → [4,2,3,8,10,12,11,7,5]
• low and high cross, swap pivot with element at crossing (8) → [4,2,3,5,10,12,11,7,8]
• Now 5 is in its final position; recursively sort left part [4,2,3] and right part [10,12,11,7,8]

Quicksort is considered one of the best general-purpose sorting algorithms.

Course Overview

The course began with arrays (fixed size limitation), then linked lists, stacks, and queues (implemented with arrays and linked lists). Stacks play a crucial role in computer runtime environments, and queues are essential for simulations.

Trees were introduced, particularly binary trees and AVL trees (balanced binary search trees). Threaded binary trees and union/find (up-tree) data structures were covered. The course emphasized Abstract Data Types (ADTs) — forming new data structures using existing ones. The table/dictionary ADT was implemented in six different ways, including skip lists. Hashing was discussed as a purely algorithmic procedure.

Important data structures not covered in detail include graphs, which are primarily important from an algorithmic perspective.

⭐ Key Takeaways

The most critical concepts from this lecture are: (1) The divide and conquer strategy splits a problem into smaller subproblems, solves them recursively, and combines results — it reduces sorting time from O(n²) to O(n log₂ n). (2) Mergesort is O(n log₂ n) but requires O(n) extra space for the temporary array, making it not in-place. (3) Quicksort is also O(n log₂ n) but is an in-place algorithm that partitions around a pivot value. (4) Both mergesort and quicksort use recursion and are significantly faster than elementary O(n²) sorts like insertion, selection, and bubble sort. (5) The course overview highlights that data structures and algorithms are complementary — algorithms bring along appropriate data structures, and choosing the right combination is a critical design skill for software engineers.

🧠 Quick Revision Questions

1. What are the three steps of the mergesort algorithm?
2. Why is mergesort not considered an in-place sorting algorithm, and what is its space complexity?
3. In quicksort, what happens when the low and high indexes cross each other during partitioning?
4. How does the time complexity of divide and conquer (using insertion sort on halves) compare to plain insertion sort for n=100?
5. What are the two key advantages of quicksort over mergesort?