Charles Cusack
Computer Science
Hope College

All Homework

Homework 1

AIDMA Problem 2.1
AIDMA Problem 2.4 (Note: You just need to rephrase the statement, not prove anything!)

Homework 2

AIDMA Problem 2.12
AIDMA Problem 2.19
AIDMA Problem 2.22
AIDMA Problem 2.23

Homework 3

AIDMA Problem 3.3 b
AIDMA Problem 3.12

Homework 4

Rank the following functions in increasing order of growth rate.
- \(7n\log n\)
- \(n^3 + 100n^2\)
- \(2^{\sqrt{n}}\)
- \(n + 5\)
- \((\log n)^2 + 3\)
- \(n!\)
- \(n^{3/2} - 100n\)
- \(3^{n}\)
- \(\sqrt{n} + \log n\)
- \(42\)
- \(n^2\log n + 50n^2\)
- \(5n^2\)
- \(0.5n\log n\)
- \(2^{n} - n^{10}\)
- \(\log\log n + 20\)
Let \( f(n) = 5n^3 + 2n^2 + 7 \). Prove that \( f(n) = \Theta(n^3) \):
1. Using the definition.
2. Using the Limit Theorem.

Homework 5

Analyze Best and Worst Case Running Times

Give tight bounds for the best and worst case running times of each algorithm in terms of input size. Unless noted, assume A.length = n. Do not worry about what the code does; only analyze how long it takes. Use standard asymptotic notation and justify briefly on your own.

Early exit on a sentinel value.

int scanUntilZero(int[] A) {
    int s = 0;
    for (int i = 0; i < A.length; i++) {
        s += A[i];
        if (A[i] == 0) break;
    }
    return s;
}

Nested search over the prefix. Early exit on first duplicate.

int hasDuplicatePrefix(int[] A) {
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < i; j++) {
            if (A[i] == A[j]) return 1;
        }
    }
    return 0;
}

Pair counting with a break depending on a threshold \(S\).

void countPairsUpToS(int[] A, int S) {
    int c = 0;
    for (int i = 0; i < A.length; i++) {
        for (int j = i + 1; j < A.length; j++) {
            c++;
            if (A[i] + A[j] > S) break;
        }
    }
}

Divide by 2 until zero.

void halfWhile(int n) {
    while (n > 0) {
        n = n / 2;
    }
}

Tricky one!

void sqrtStepper(int n) {
    for (int i = 1; i * i <= n; i++) {
        // O(1) work
    }
}

Changing inner loop.

void doublingInner(int n) {
    for (int i = 1; i <= n; i++) {
        int k = 1;
        while (k < i) {
            k = k * 2;
        }
    }
}

Triangular nested loop with a possible early break based on a changing accumulator.

void triangularPlusBreak(int n) {
    int t = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            t += i + j;
            if (t % 1000 == 0) break;
        }
    }
}

Fixed-size inner loop of constant \(M\) iterations.

int fixedInnerConstant(int[] A) {
    int M = 250; // constant
    int s = 0;
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < M; j++) {
            s += A[i] + j;
        }
    }
    return s;
}

Two separate parameters: total work depends on both \(n\) and \(m\).

void twoParameters(int n, int m) {
    int x = 0;
    for (int i = 0; i < n; i++) x++;
    for (int j = 0; j < m; j++) x++;
}

Fully nested two-parameter loops.

void nestedTwoParameters(int n, int m) {
    long x = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            x += i + j;
        }
    }
}

Three nested loops with possible immediate return.

void threeNestedWithBreak(int n) {
    long x = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            for (int k = 0; k < j; k++) {
                x++;
                if (x == 5) return;
            }
        }
    }
}

Mixed for/while.

void mixedForWhile(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        int t = i;
        while (t > 0) {
            t = t / 3;
            count++;
        }
    }
}

Early exit when a running sum exceeds a threshold; otherwise full scan.

int sumWithSentinel(int[] A) {
    int s = 0;
    for (int i = 0; i < A.length; i++) {
        s += A[i];
        if (s > 1000000) return s;
    }
    return s;
}

Work per iteration grows with the index: total work is the sum.

void variableWorkPerIter(int n) {
    for (int i = 1; i <= n; i++) {
        for (int t = 0; t < i; t++) {
            // 1 step per t
        }
    }
}

Homework 6

(10) Do the Sorting Comparison Assignment.
You may work in pairs on this assignment.

Homework 7

Max Solvable Input Size: Assume your algorithm for Subeset Sum runs in \( 5n \cdot 2^n \) steps and your machine processes 100 million steps/second. Estimate the largest value of \( n \) solvable in 1 second, 1 hour, 1 day, 1 month, and 1 year. Show your work. (Hint: You might want to use a spreadsheet to help you with the calculations. If so, make sure what you submit has enough details printed so I can determine the formulas.)
Subarray Sum Match: Given an array of positive integers \( A[0 \dots n-1] \) and an integer target value \( k \), find all contiguous subarrays whose elements sum to exactly \( k \). (A contiguous subarray is a subset consisting of all of the elements from some index \(i\) to some index \(j\geq i\).)
1. Design and write a brute-force algorithm using a nested loop to solve this problem.
2. What are the best-case and worst-case time complexities?
3. Apply your algorithm to the example \( A = [1, 5, 2, 7, 4, 2, 5] \) with \( k = 10 \). Show all subarrays considered.

Homework 8

(8) Complete the Kevin Bacon Assignment. You may work in pairs on this problem, but not on the rest of the assignment.
(6) Run DFS on the following DAG. Process the vertices in alphabetical order, both in the overall algorithm and the adjacency lists! Print/copy/redraw the graph and write the timestamps on the nodes.
1. Show the discovery and finishing timestamps for every vertex.
2. Classify every edge (tree, back, forward, cross).
3. List the vertices in decreasing order of their finishing times (largest finish time first). In fact, redraw the graph with the vertices lined up in that order.
4. Observation: What special property does the ordering from part (c) have for a DAG? State it in one sentence and explain why it holds using the DFS timestamps.
(6) Design a decrease-by-half algorithm that computes ⌊log₂ n⌋. Do not forget to give the work case complexity!
Note: Do not look up an algorithm. Come up with your own!

Homework 9

Not available yet.

Homework 10

Not available yet.