Advanced Data Structures and Algorithms Course Outline

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.