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 minute, 1 hour, 1 day, 1 month, 1 year, 100 years, and 1000 years. 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) Problem 10 from BFS (Even-Length Cycle Detection via BFS).

Homework 9

Let \(T(n)\) be defined by \(T(1)=1\) and \(T(n) \;=\; 4\,T\!\left(\frac{n}{3}\right) + n\), where \(n = 3^k\), for \(k=0,1,2,\ldots\)
For this assignment, you will show that the solution to this recurrence relation is
- \(T(n)=4\,n^{\log_3 4}-3n\), or
- \(T(3^k)=4^{\,k+1}-3^{\,k+1}\), or
- \(T(n)=\Theta(n^{\log_3 4})\),
where the first two formulas are equivalent, one expressed in terms of \(n\) and the other in terms of \(k\) (Remember, we are assuming \(n = 3^k\)), and the third is a bound. For each of the following, choose the form of the answer that is easiest to work with for that given proof type.
1. Prove the given result using Iteration (also called backward substitution).
2. Prove the given result using Substitution (prove it by induction).
3. Prove the given result using the Master Theorem.

Homework 10

(10) Homework Problem 5 from Strassen's Algorithm (Hands-on Strassen multiplying 4x4 matrices.)
(10) Homework Problem 6 from Divide-and-Conquer (Weight Calibration).

Homework 11

(10) Complete the Convex Hull Assignment. You may work in pairs on this problem.

Homework 12

Not available yet.

Homework 13

Not available yet.

Homework 14

Not available yet.

Homework 15

Not available yet.