Digging Around In Arrays
Digging Around In Arrays
Copyright © 2015 Bart Massey
Consider the following problem:
FIRST LONG 1-STRING
INSTANCE: A one-based array a of n elements, with the elements drawn from the set {0, 1}. An integer lower bound m.
SOLUTION: The index of the first position in a such that there is a string of m 1s starting at that position. That is: a position i in a such that a[i..i+m-1] are all 1s and there is no position j < i in a with this property. If there is no string of m 1s in a, fail.
1.1. Give an algorithm that solves this problem. As always, argue its correctness.
1.2. What is the worst-case O(n,m) running time of your algorithm? Why?
1.3. What is the best-case Ω(n,m) running time of your algorithm? Why?
1.4. Non-required BONUS: Find an algorithm with Θ(n/m) average-case complexity, assuming a uniform distribution of inputs. What is the worst-case complexity of this algorithm? What is a worst-case instance? A best-case instance?
Note: This problem came up for me recently; I was trying to build tests for a hardware random number generator.
Consider the following problem:
ARRAY INTERSECTION
INSTANCE: One-based arrays a and b of positive integers. Denote the size of a by |a| and similarly for b.
SOLUTION: A one-based array c of positive integers, such that c contains exactly one copy of each integer that appears somewhere in both a and b. Thus, |c| ≤ min(|a|, |b|).
2.1. Give a worst-case O(|a| lg |a| + |b| lg |b|) algorithm solving this problem.
2.2. Generalize the problem description to allow for an arbitrary number of input arrays. (This involves choosing an appropriate representation for a collection of arrays.)
2.3. Give an algorithm for the generalized problem.
2.4. Implement the two-array algorithm in your favorite programming language.
2.5. Devise tests for the two-array algorithm. Use these tests both to check correctness and to measure the running time on various size inputs. How does the running time grow in practice?
Note: The generalized version of this problem came up just now for me; I was working on a video control application. I implemented an O(n3) algorithm, though, since the array sizes were quite small.