Cantor's Diagonalization and Knuth's Algorithms Guide

Cantor's Diagonalization

Theory

Cantor's Diagonalization is a mathematical technique used to prove that some infinite sets are "bigger" than others. Most famously used to prove that real numbers are uncountable.

Implementation (Basic Concept)

function cantorDiagonalization(sequences, n) {
    // Create a new sequence different from all given sequences
    let newSequence = '';
    
    for (let i = 0; i < n; i++) {
        // Get the i-th digit of the i-th sequence
        const digit = sequences[i][i];
        
        // Make this digit different
        newSequence += digit === '0' ? '1' : '0';
    }
    
    return newSequence;
}

// Example usage
const sequences = [
    "01010101",
    "11111111",
    "00000000",
    "10101010"
];

console.log(cantorDiagonalization(sequences, 4));

Applications

1. Proving uncountability of real numbers
2. Halting problem proof
3. Set theory arguments
4. Computational complexity theory

Knuth's Essential Algorithms

1. Dancing Links (Algorithm X)

Used for exact cover problems, particularly in solving Sudoku and pentomino puzzles.

class DLX {
    constructor() {
        this.header = new Node('header');
        this.solution = [];
    }
    
    addColumn(name) {
        const node = new Node(name);
        node.right = this.header.right;
        node.left = this.header;
        this.header.right.left = node;
        this.header.right = node;
        return node;
    }
    
    search(k) {
        if (this.header.right === this.header) {
            return this.solution;
        }
        
        // Choose column with minimum size
        let column = this.chooseColumn();
        this.cover(column);
        
        // Try each row
        let row = column.down;
        while (row !== column) {
            this.solution[k] = row;
            
            // Cover columns
            let j = row.right;
            while (j !== row) {
                this.cover(j.column);
                j = j.right;
            }
            
            this.search(k + 1);
            
            // Uncover columns
            j = row.left;
            while (j !== row) {
                this.uncover(j.column);
                j = j.left;
            }
            
            row = row.down;
        }
        
        this.uncover(column);
        return null;
    }
}

2. Knuth-Morris-Pratt (String Matching)

Efficient pattern matching algorithm.

function computeLPS(pattern) {
    const lps = new Array(pattern.length).fill(0);
    let len = 0;
    let i = 1;
    
    while (i < pattern.length) {
        if (pattern[i] === pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len !== 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    return lps;
}

function KMP(text, pattern) {
    const lps = computeLPS(pattern);
    const matches = [];
    let i = 0;  // text index
    let j = 0;  // pattern index
    
    while (i < text.length) {
        if (pattern[j] === text[i]) {
            i++;
            j++;
        }
        
        if (j === pattern.length) {
            matches.push(i - j);
            j = lps[j - 1];
        } else if (i < text.length && pattern[j] !== text[i]) {
            if (j !== 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    
    return matches;
}

3. MMIX Assembly Language

Knuth's ideal computer architecture. Key concepts:

1. Registers:

   • 256 general-purpose registers
   • Special registers (rA, rB, rC, rD, rE, rF, rG, rH)
   • Local registers (l0-l7)

2. Basic Operations:

// MMIX simulator (basic operations)
class MMIX {
    constructor() {
        this.registers = new Array(256).fill(0n);
        this.memory = new Map();
    }

    ADD(x, y, z) {
        this.registers[x] = (this.registers[y] + this.registers[z]) & ((1n << 64n) - 1n);
    }

    MUL(x, y, z) {
        this.registers[x] = (this.registers[y] * this.registers[z]) & ((1n << 64n) - 1n);
    }

    LOAD(x, y, z) {
        const address = Number(this.registers[y] + this.registers[z]);
        this.registers[x] = this.memory.get(address) || 0n;
    }

    STORE(x, y, z) {
        const address = Number(this.registers[y] + this.registers[z]);
        this.memory.set(address, this.registers[x]);
    }
}

4. Combinatorial Algorithms

Key techniques from TAOCP Volume 4:

// Algorithm L: Lexicographic Combinations
function nextCombination(arr, n) {
    const j = arr.length - 1;
    if (arr[j] < n) {
        arr[j]++;
        return true;
    }
    
    let i = j - 1;
    while (i >= 0 && arr[i] + 1 === arr[i + 1]) {
        i--;
    }
    
    if (i < 0) return false;
    
    arr[i]++;
    for (let k = i + 1; k <= j; k++) {
        arr[k] = arr[i] + (k - i);
    }
    return true;
}

// Algorithm P: Plain Changes (Gray Code)
function grayCode(n) {
    const codes = [];
    const size = 1 << n;
    
    for (let i = 0; i < size; i++) {
        codes.push(i ^ (i >> 1));
    }
    
    return codes;
}

Time Complexity Analysis

1. Dancing Links

   • Time: O(branches^depth)
   • Space: O(n^2)

2. KMP Algorithm

   • Preprocessing: O(m)
   • Search: O(n)
   • Space: O(m)

3. Combinatorial Algorithms

   • Next Combination: O(n)
   • Gray Code: O(2^n)

Common Applications

1. Dancing Links

   • Sudoku solving
   • Exact cover problems
   • Pentomino puzzles
   • N-Queens problem

2. KMP

   • Text processing
   • Pattern matching
   • DNA sequence matching
   • Log file analysis

3. Combinatorial Algorithms

   • Permutation generation
   • Combination enumeration
   • Gray code generation
   • Backtracking problems

Implementation Tips

1. Dancing Links

   • Use circular doubly-linked lists
   • Implement column headers with size counters
   • Consider sparse matrix representation

2. KMP

   • Preprocess pattern first
   • Handle pattern length > text length
   • Consider multiple pattern matching

3. MMIX

   • Use BigInt for 64-bit operations
   • Implement proper overflow handling
   • Consider pipeline effects

4. Combinatorial Algorithms

   • Use iterative over recursive when possible
   • Implement efficient bit operations
   • Consider memory usage for large sets