Practice & self-check
Supplementary questions based on the supplied topics. Original questions also remain in each lecture’s complete source section. These are study exercises, not claimed past exam papers.
Git & the working environment
1. Does git add upload a file to GitHub?
Worked answer. No. It stages a local snapshot for the next commit. Uploading committed history requires a separate push to a configured remote.
2. Why keep an algorithm experiment on a branch?
Worked answer. It separates the experiment from the baseline and makes it possible to compare, discard or merge the changes intentionally.
Thinking in algorithms
1. How is an algorithm different from a Java program?
Worked answer. The algorithm describes the abstract steps. The Java program implements them using particular language features, types and runtime behavior.
2. Why is binary search not automatically better for an unsorted array?
Worked answer. It requires sorted input. Sorting has a cost; a single linear scan may be cheaper for one query.
Java setup & first programs
1. Why can java work while javac is not found?
Worked answer. The terminal may be finding a runtime without the compiler, or PATH may point to a different installation. Verify the JDK and both command locations.
2. Where does Euclid receive 48 and 18 in java Euclid 48 18?
Worked answer. They arrive as strings in args[0] and args[1], which main parses into integers.
Euclid’s algorithm & recursion
1. Trace gcd(1071, 462).
Worked answer. 1071 mod 462 = 147; 462 mod 147 = 21; 147 mod 21 = 0. The GCD is 21.
2. Why must gcd2 save q in temp?
Worked answer. The next p must be the previous q. Once q is replaced with the remainder, that old value would otherwise be lost.
Measuring & modelling algorithms
1. A run takes 2 seconds at n and 16 seconds at 2n. What exponent does the doubling hypothesis suggest?
Worked answer. The ratio is 8, so b = log₂8 = 3. This suggests a cubic power law, but more measurements and a mathematical argument are needed.
2. Why is 3-SUM’s triple count n(n−1)(n−2)/6?
Worked answer. Each unordered selection of three distinct indices is visited exactly once because i < j < k. Dividing ordered selections by 3! gives the count.
3. Does Θ(n³) running time imply Θ(n³) memory?
Worked answer. No. Time counts work; space counts simultaneously stored data. The brute-force 3-SUM loop uses constant auxiliary space.
Union–find & dynamic connectivity
1. Why must weighted union compare sizes at roots?
Worked answer. Only a root’s stored size represents the entire component. A non-root’s size may be stale after its tree is attached elsewhere.
2. Can union–find directly support deleting an arbitrary connection?
Worked answer. The standard structures here support merges but not efficient arbitrary splitting. Removing an edge may require a different dynamic connectivity approach.
3. Does amortized O(α(n)) mean every operation takes constant time?
Worked answer. No. It is a bound on aggregate cost over a sequence, expressed using a slowly growing function.
Asymptotic analysis & growth rates
1. Prove 4n² + 3n + 7 is Θ(n²).
Worked answer. For n ≥ 1, 4n² ≤ 4n² + 3n + 7 ≤ 14n². Constants c₁ = 4, c₂ = 14 and n₀ = 1 establish the claim.
2. What is the cost of repeatedly doubling i from 1 while i < n?
Worked answer. After k iterations i = 2ᵏ, so k is about log₂ n. With constant work per iteration, the time is Θ(log n).
Stacks, queues & amortized analysis
1. Push A, push B, pop, push C, pop. What is returned?
Worked answer. The first pop returns B, and the second returns C. A remains on the stack.
2. Why shrink at one-quarter occupancy rather than one-half?
Worked answer. It leaves room between growth and shrink thresholds, preventing a short alternating sequence from forcing repeated linear-time copies.
3. What is the result of ( 8 - ( 6 / 3 ) )?
Worked answer. 6. The inner division is 6 / 3 = 2, and the outer subtraction is 8 − 2. Popping operands in the wrong order would change the result.