Algorithm and Data Structure Analysis

In this assignment, you will practice reading programs and determining the runtime and space complexities they require. You will also get some practice writing short programs that adhere to specified complexity guarantees.

Topics: Java Collections & Algorithm Efficiency

Due Date: February 14 @ 11:59 PM

Question 1

Below are two functions A and B.

Snippet A:

public static double A(List<Integer> lst) {
    if (lst.size() < 1) {
        throw new IllegalArgumentException("List can't be empty.");
    }
    int middle = lst.size() / 2;
    return lst.get(middle);
}

Snippet B:

public static double B(List<Integer> lst) {
    if (lst.size() <= 1) {
        throw new IllegalArgumentException("List must have at least two elements.");
    }

    int first = lst.get(0);
    lst.remove(0);
    int last = lst.get(lst.size() - 1);
    lst.remove(lst.size() - 1);
    return (first + last) / 2;
}

When discussing these functions, Lily and Jeremy get into an argument. Lily claims that A will run in \(O(N)\) time whereas B runs in \(O(1)\) time. Jeremy thinks the opposite is true: A is constant time and B is linear time. (In both cases, let \(N\) refer to the length of the input list.)

Help them get to the bottom of this. Are they both wrong, or perhaps both right? Is only one of them correct? Why?

Question 2

Examine the following program which takes three Lists as input, each one containing N 13-digit IDs. The program is designed to return true if there is an ID that appears in all three Lists and false otherwise. There can be repeated IDs within a List, although this doesn’t count towards making a “triple”.

public static boolean hasTriples(List<String> one, List<String> two, List<String> three) {

    for (String s1 : one) {
        for (String s2 : two) {
            if (s1.equals(s2)) {
                if (three.contains(s1) && three.contains(s2)) {
                    return true;
                }
            }
        }
    }
    return false;
}

Part 1:

What is the best-case runtime complexity of this program? What is the worst-case runtime complexity of this program? Explain your answer for both.

Part 2:

Write a version of this program that has a better worst-case runtime complexity than \(O(N^2)\). What is the runtime complexity of your version and why?

Question 3

Here is an algorithm for finding the top \(k\) largest elements contained in an Iterator over \(n\) elements.

Algorithm A:

public static <T extends Comparable<T>> List<T> topK(int k, Iterator<T> iter) {
        TreeSet<T> set = new TreeSet<>();
        while (iter.hasNext()) {
            set.add(iter.next());
        }

        List<T> output = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            output.add(set.pollLast());
        }
        return output;
    }

Part 1:

What are the runtime and space complexities of this function? Explain your answers. (Ignore the space complexity of the Iterator that you’re provided as input; only consider the additional space requirements that your program generates.)

Part 2:

Write an algorithm to solve this problem that uses \(O(k)\) space complexity. What is the runtime complexity of your algorithm? Explain.

Submission

Please submit your homework as a PDF to Gradescope!