---
title: "Advanced Data Structures and Algorithms Course Outline"
lastModified: "2026-10-07T11:38:29+05:30"
---

The sources provide a comprehensive overview of several advanced data structures and algorithms. Below is an organized list of the topics and subtopics covered:

**I. Advanced Sorting Algorithms**
*   **Simple Sorting Algorithms**
    *   Bubble sort
    *   Selection sort
    *   Insertion sort
        *   Issue: Too many copies for small items on the far right
*   **Advanced Sorting Algorithms**
    *   **Merge Sort**
        *   **Characteristics**:
            *   Recursive algorithm
            *   Time complexity: O(n\*logn)
            *   Fairly easy to implement (easier than Quick sort and Shell sort)
            *   Downside: Requires an additional array in memory equal in size to the one being sorted
        *   **Merging Two Sorted Arrays**:
            *   The core of the merge sort algorithm
            *   Creates a third array (C) from two already sorted arrays (A and B)
            *   Detailed steps with example (comparisons and copies)
            *   Java code implementation (`main`, `merge`, `display` methods)
            *   Explanation of the `merge()` method's three while loops
        *   **Sorting by Merging**:
            *   Idea: Divide an array in half, sort each half, merge the two halves
            *   Recursion is used to sort each half
            *   Process involves dividing until a sub-array with one element (base case)
            *   Example illustration of the sorting process
            *   Merge Sort algorithm structure (`mergeSort` method)
    *   **Shell Sort**
        *   **Introduction**:
            *   Named for Donald L. Shell (1959)
            *   Based on insertion sort, with improved performance
            *   Time complexity: O(n\*(logn)^2)
            *   Faster than O(n^2) sorts but not as fast as Quick sort and Merge sort
            *   Good for medium-sized arrays (e.g., up to a few thousand items)
            *   Does not use extra memory space
            *   Worst-case performance is not significantly worse than average performance
            *   Some experts recommend starting with Shell Sort for almost any project
        *   **h-Sorting (or n-sorting)**:
            *   Achieves large shifts by insertion-sorting widely spaced elements
            *   Spacing is called the increment or gap (h)
            *   Example with h = 4 for a 10-item array, sorting elements at intervals
        *   **Diminishing Gaps**:
            *   Initial interval should be large for larger arrays
            *   Interval is repeatedly reduced until it becomes 1
            *   Sequence of numbers used is called the interval sequence or gap sequence
        *   **Knuth's Interval Sequence**:
            *   Generated by the recursive expression `h = 3*h + 1` (in reversed form, starting from 1)
            *   Initial gap is found based on array size
            *   Gap reduced using `h = (h–1)/3` until `h=1`
        *   **Other Interval Sequences**:
            *   Requirement: Sequence must end with 1
            *   Shell's original suggestion: N/2, divided in half for each pass
            *   Variation: Divide each interval by 2.2 instead of 2
            *   Another possibility: `if (h < 5) h = 1; else h = (5*h-1) / 11;`
        *   **Shell Sort Program** (Java code structure)
        *   **Efficiency of the Shell Sort**:
            *   No theoretical analysis except in special cases
            *   Experimental estimates range from O(n^3/2) down to O(n^7/6)
    *   **Quick Sort**
        *   Mentioned as an advanced sorting algorithm
        *   Time complexity: O(N\*logN)
        *   Worst-case performance can be much worse than average performance unless precautions are taken
    *   **Comparison and Non-Comparison Sorting**
        *   Counting Sort
        *   Radix Sort

**II. Red-Black Trees**
*   **Binary Trees**
    *   Combine advantages of ordered arrays (quick search) and linked lists (quick insertion/deletion)
*   **The Problem with Binary Trees**:
    *   Suffer when data is inserted in already-sorted or inversely sorted order
    *   Becomes unbalanced, losing ability for quick find/insert/delete
    *   Maximally unbalanced trees (nodes arrange in a line, like a linked list)
    *   Search speed reduced to O(n) instead of O(log n)
*   **Self-Balancing Binary Search Tree**:
    *   Guarantees O(log n) search times
    *   Each node has roughly the same number of descendants on its left and right sides
    *   Automatically keeps its height small during insertions/deletions
    *   Types of self-balancing trees:
        *   2–3 Tree
        *   2-3-4 Tree (2-4 Tree)
        *   AA Tree
        *   AVL Tree
        *   B-Tree
        *   **Red–Black Tree (R-B Tree)**
*   **Red-Black Tree Characteristics / Properties**:
    *   Balance achieved during insertion
    *   Corrective actions (restructuring) if characteristics violated
    *   **Nodes are colored** (either red or black)
    *   **Rules to preserve color arrangements**:
        1.  Every node is either red or black
        2.  The root is always black
        3.  If a node is red, its children must be black (Red Node Constraint)
        4.  Every path from the root to a leaf (or null child) must contain the same number of black nodes (black height must be the same)
    *   **NIL Nodes / Null Child**:
        *   Potential child attachment points, considered black
    *   Fixing violations: Change node colors, perform rotations
        *   Changing color: Red to black or vice versa
        *   Rotation: Rearrangement of nodes for balance
    *   Newly inserted nodes are always colored red (except root)
*   **Insertions in Red-Black Trees**
    *   Examples of insertions and how rules are maintained or violated
    *   Illustrates color flips and potential rotations
*   **Rotations and Color Flips of RB Trees**
*   **Deletion of RB Trees**
*   **Java Implementation**
    *   `RedBlackNode` class (key, parent, left, right, numLeft, numRight, color)
    *   `RedBlackTree` class (root, nil node)
    *   **Key Methods and Logic**:
        *   `insert(T key)`
        *   `insert(RedBlackNode<T> z)`
        *   `insertFixup(RedBlackNode<T> z)`
        *   `leftRotate(RedBlackNode<T> x)`
        *   `rightRotate(RedBlackNode<T> y)`
        *   `leftRotateFixup(RedBlackNode x)`
        *   `rightRotateFixup(RedBlackNode y)`
        *   `remove(RedBlackNode<T> v)`
        *   `removeFixup(RedBlackNode<T> x)`
        *   `treeMinimum(RedBlackNode<T> node)`
        *   `treeSuccessor(RedBlackNode<T> x)`
        *   `search(T key)`
        *   `numGreater(T key)`
        *   `numSmaller(T key)`
        *   `findNumGreater(RedBlackNode<T> node, T key)`
        *   `findNumSmaller(RedBlackNode<T> node, T key)`
        *   `getGreaterThan(T key, Integer maxReturned)`
        *   `isNil(RedBlackNode node)`
        *   `size()`
        *   `fixNodeData(RedBlackNode<T> x, RedBlackNode<T> y)`
*   **Applications of Red-Black Trees in Computing**
    *   Maintaining sorted data efficiently
    *   Logarithmic time complexity for all necessary operations (insertion, deletion, search, finding elements)

**III. Hash Tables**
*   **Introduction**
    *   Offers very fast insertion and searching (close to constant time: O(1))
    *   Used when fast searching is highly essential (e.g., spelling checkers)
    *   Relatively easy to program
*   **Disadvantages of Hash Tables**
    *   Based on arrays, which are difficult to expand
    *   Performance degrades catastrophically when a table becomes too full
    *   No convenient way to visit items in order
*   **Back to Arrays**
    *   Random access is a key feature (O(1) if index is known)
    *   Ideal if search key is the same as array index (e.g., student ID, employee ID)
    *   Keys are not always well-organized (e.g., dictionary words)
*   **Hash Function**
    *   System for turning a key (like a word) into an appropriate index number
    *   **Converting Words to Numbers**:
        *   Simple addition of character codes (e.g., 'cats' to 43)
            *   Problem: Too many words have the same index (collisions)
            *   Array too small, doesn't discriminate enough
        *   Multiplying by powers (e.g., powers of 27 for letters)
            *   Generates a unique number for every potential word
            *   Problem: Range of numbers becomes too large for memory
    *   **Hashing concept**:
        *   Compresses a huge range of numbers into a smaller array index range
        *   Uses the modulo operator (`%`)
        *   `arrayIndex = hugeNumber % arraySize`
        *   An array using a hash function is called a hash table
    *   **Purpose of a hash function**: To transform key values into index values, distributing them randomly across the hash table
    *   **Features of a Good Hash Function**:
        *   Simple and Fast
        *   Don’t Use Non-Data (redundant parts of a key)
        *   Use All the Data (every part of key contributes)
        *   Use prime number as table size
    *   **Perfect Hash Function**: Maps every key into a different table location
    *   **Random Keys**: `index = key % arraySize` is satisfactory
    *   **Non-Random Keys**: Require work to ensure randomness
    *   **Hashing Strings**:
        *   Convert short strings to key numbers by multiplying digit codes by powers of a constant
        *   Can use Horner's method for efficiency
    *   **Folding**:
        *   Breaking key into groups of digits and adding them
        *   Ensures all digits influence hash value
        *   Number of digits in group corresponds to array size
        *   Example: Social Security numbers
*   **Collisions**
    *   Occurs when two different keys hash to the same index
    *   **Resolution Techniques**:
        *   **Open Addressing**:
            *   When a data item can't be placed at the calculated index, another location is sought
            *   **Linear Probing**:
                *   Vacant cells searched sequentially (incrementing index by 1)
                *   **Clustering**: As array gets full, clusters grow, leading to long probe lengths and slow access
                *   Recommended to keep array less than half or two-thirds full
            *   **Quadratic Probing**:
                *   Probes go to x+1^2, x+2^2, x+3^2, etc.
                *   Eliminates **primary clustering**
                *   Suffers from **secondary clustering** (keys hashing to same cell follow same sequence)
            *   **Double Hashing**:
                *   Eliminates primary and secondary clustering
                *   Uses a second, different hash function for the step size
                *   Step size is constant for a given key but different for different keys
                *   Secondary hash function must not be primary, and never output 0
                *   Recommended form: `stepSize = constant - (key % constant)` where `constant` is prime and smaller than array size
                *   **Requires prime table size** to ensure all cells are visited
        *   **Separate Chaining**:
            *   Installs a linked list at each index in the hash table
            *   Colliding items are simply added to the linked list at that index
*   **Expanding the Array (Rehashing)**
    *   Create a new, larger array and re-insert contents of old array
    *   Items won't be in the same place due to new array size
    *   Takes linear time
*   **Load Factor**:
    *   Ratio of number of items (`nItems`) to table size (`arraySize`)
    *   `loadFactor = nItems / arraySize`
    *   Can be 1 or greater in separate chaining
*   **Prime Number for Table Size**:
    *   Important for any hashing system to avoid clustering
    *   Ensures probe sequence eventually checks every cell
*   **Hashing Efficiency**:
    *   Approaches O(1) if no collisions
    *   Proportional to probe length if collisions occur
    *   Depends on load factor
    *   **Linear Probing**:
        *   Successful search: `P = ( 1 + 1 / (1 – L)^2 ) / 2`
        *   Unsuccessful search: `P = ( 1 + 1 / (1 – L) ) / 2`
        *   Performance degrades seriously at high load factors
    *   **Quadratic Probing and Double Hashing**:
        *   Modest superiority over linear probing
        *   Successful Search: `P = -log2(1-L) / L`
        *   Unsuccessful search: `P = 1 / (1-L)`
        *   Can tolerate somewhat higher load factors
    *   **Separate Chaining**:
        *   Average list length equals load factor
        *   Searching (successful): `1 + loadFactor / 2`
        *   Searching (unsuccessful): `1 + loadFactor` (if unordered lists)
        *   Insertion (unordered lists): O(1)
        *   Insertion (ordered lists): `1 + loadFactor / 2`
*   **Open Addressing vs. Separate Chaining**:
    *   Double hashing preferred for open addressing
    *   Linear probing simpler to implement
    *   Separate chaining preferable when number of items unknown

**IV. Heaps**
*   **Priority Queues and Heaps**
    *   Priority queues offer easy access to smallest (or largest) item
    *   Used in computer task scheduling, weapon systems, Dijkstra's algorithm
    *   Heap is a data structure to implement a priority queue
    *   Heap is a kind of tree
    *   Insertion and deletion in O(logn) time
    *   Good for priority queues with many insertions
    *   Priority Queue is an ADT implemented by Heap
*   **Heap Characteristics**:
    *   Complete binary tree (completely filled from left to right)
    *   Usually implemented as an array
    *   Heap condition: Every node's key is larger than (or equal to) children's keys (assuming max-heap)
    *   Weakly ordered compared to binary search trees
    *   Traversing nodes in order is difficult
    *   Does not allow convenient searching for a specified key
*   **Removal (Deletion) in Heaps**
    *   Removes the node with the maximum key (always the root)
    *   Steps:
        1.  Remove the root
        2.  Move the last node into the root
        3.  Trickle the last node down until it's in proper position
    *   Trickle-down algorithm: Swaps target node with the larger child
    *   Java code example (`remove()`, `trickleDown()` methods)
*   **Insertion in Heaps**
    *   Places new node in first open position at array end
    *   Trickle-up algorithm: Swaps new node with its parent if new node's key is larger
    *   Java code example (`insert()`, `trickleUp()` methods)
*   **Trickle Up and Trickle Down Operations**
*   **Expanding the Heap Array**
    *   Create new, larger array and copy data
    *   Unlike hash tables, doesn't require reordering data
    *   Copying takes linear time
*   **Efficiency of Heaps (Heap Operations)**
    *   Trickle-up and trickle-down are most time-consuming
    *   Comparisons and node copies involved
    *   Generally, heap operations take O(logN) time (L = log2N+1 levels)
*   **Heapsort**
    *   Algorithm: Insert all unordered items into a heap, then repeatedly remove them
    *   Time complexity: O(N\*logN)
    *   Not quite as fast as quicksort but comparable
    *   **Tricks for efficiency**:
        *   **Trickling Down in Place**:
            *   Rearrange an unordered array into a heap with N/2 applications of `trickleDown()`
            *   Start `trickleDown()` from the rightmost node with children ((N/2)-1) and work upward
        *   **Using the Same Array**:
            *   Ordered array and heap array can share the same memory space during sorting
            *   Removed items are placed in the newly freed cells at the end of the heap array

**V. Graphs and Graph Algorithms**
*   **Introduction to Graphs**
    *   Represents relationships between pairs of objects
    *   Consists of nodes (vertices) and edges
    *   Shape dictated by physical or abstract problem (e.g., cities and airline routes)
*   **Seven Bridges of Königsberg** (a historically notable problem that laid foundations of graph theory)
*   **Applications of Graphs**:
    *   Google Maps (transportation systems, shortest path algorithms)
    *   Facebook (friend suggestions)
    *   E-commerce websites (recommendations)
*   **Vertices and Edges (Terminology)**
    *   Graph G defined as G=(V,E)
    *   V(G): finite, non-empty set of vertices
    *   E(G): set of edges (pairs of vertices)
    *   **Adjacency**: Two vertices connected by a single edge (neighbors)
    *   **Paths**: A sequence of edges
    *   **Connected Graphs**: At least one path from every vertex to every other vertex
    *   **Directed Graphs**: Edges have directions
    *   **Weighted Graphs**: Edges have a numerical weight (e.g., distance, time, cost)
*   **Graph Implementation (Representation of Graphs)**:
    *   Vertex objects can be placed in an array
    *   Two common approaches for edges:
        *   **Adjacency Matrix**: A two-dimensional NxN array indicating edge presence
        *   **Adjacency List**: An array of lists, where each list shows adjacent vertices
*   **Graph Searching (Traversal)**:
    *   Finding which vertices can be reached from a specified vertex
    *   Finding a path between two nodes
    *   Two methods:
        *   **Depth-First Search (DFS)**:
            *   Travels as far as possible down a path
            *   Uses a **stack**
            *   Rules: visit unvisited adjacent vertex (mark, push), pop vertex from stack if no unvisited, done if no rules apply
        *   **Breadth-First Search (BFS)**:
            *   Looks at all possible paths at the same depth before going deeper
            *   Uses a **queue**
            *   Rules: visit next unvisited adjacent vertex (mark, insert into queue), remove vertex from queue if no unvisited, done if queue is empty
*   **Minimum Spanning Tree** (mentioned as a topic)
    *   Kruskal's algorithm for finding it
*   **Shortest-Path Algorithms** (mentioned as a topic)
    *   Dijkstra's algorithm (implemented using priority queues)

**VI. Other Topics / General Concepts**
*   **Data Structures and Algorithms**
    *   Benefits of learning
    *   Time complexities (O(n^2), O(n\*logn), O(n\*(logn)^2))
*   **Blockchain Technology**
    *   Needs special cryptographic hash functions (SHA-256, Keccak-256)
*   **Handling Big Data**
    *   Distributed Systems (Chord, Kademlia)
    *   Similar Item Search (Locality-Sensitive Hashing - LSH)
    *   Smart Memory Use (Bloom filters)
    *   Speed at Scale
*   **Module Learning Outcomes (MLOs)**
    *   Describe concepts of advanced data structures/algorithms (MLO1)
    *   Utilize in programming problem-solving (MLO2)
    *   Create advanced data structures/algorithms (MLO3)
    *   Compare efficiency (MLO4)
*   **Program Learning Outcomes (PLOs)** (related to the academic program)

This outline covers all the main topics and subtopics discussed in the provided sources.