3.3 & 3.5 Homework Hacks

Homework 3.3 & 3.5

Homework 3.3

%%js
// Method to calculate Fibonacci using dynamic programming with optimized space
function fibonacci(n) {
    // Base cases for Fibonacci
    if (n === 0) return 0;
    if (n === 1) return 1;

    // Variables to store previous two Fibonacci numbers
    let prev1 = 1, prev2 = 0;
    let current = 0;

    // Iteratively calculate Fibonacci
    for (let i = 2; i <= n; i++) {
        current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }

    return current;
}

// Efficient matrix exponentiation approach (O(log n))
function fibonacciMatrix(n) {
    if (n === 0) return 0;
    
    let F = [[1, 1], [1, 0]];
    power(F, n - 1);

    return F[0][0];
}

// Helper method to perform matrix exponentiation
function power(F, n) {
    if (n === 0 || n === 1) return;

    let M = [[1, 1], [1, 0]];

    power(F, Math.floor(n / 2));
    multiply(F, F); // Square the matrix

    if (n % 2 !== 0) multiply(F, M); // Multiply by M if n is odd
}

// Matrix multiplication helper
function multiply(F, M) {
    let x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    let y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    let z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    let w = F[1][0] * M[0][1] + F[1][1] * M[1][1];

    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

// Main function to execute both Fibonacci calculations
function main() {
    let n = 50;

    // Using dynamic programming with optimized space
    console.log("Fibonacci number at position " + n + " using DP is: " + fibonacci(n));

    // Using matrix exponentiation (O(log n))
    console.log("Fibonacci number at position " + n + " using Matrix Exponentiation is: " + fibonacciMatrix(n));
}

// Run the main function
main();

<IPython.core.display.Javascript object>