Algorithm Analysis

Slides

Implementations

The maximum subsequence sum algorithm

Computing the exponentiation of a number

Recursive Factorial Algorithm

public static long factorial(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

Counting the number of binary digits Recursive Algorithm

public static int countBits(int n) {
    if (n == 0) {
        return 0;
    } else {
        return 1 + countBits(n / 2);
    }
}

The Tower of Hanoi Recursive Algorithm

public static void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        System.out.println("Move disk 1 from " + from + " to " + to);
    } else {
        hanoi(n - 1, from, aux, to);
        System.out.println("Move disk " + n + " from " + from + " to " + to);
        hanoi(n - 1, aux, to, from);
    }
}