Algoritmika 2026/27 sügis

HW1. Algorithmic Evidence: Prediction, Measurement, and Explanation

Deadline: Monday, 07.09.2026, 23:59

Purpose

Algorithmics is not only about implementing an algorithm. We must predict how an algorithm should behave, decide what evidence could challenge that prediction, measure it fairly, and explain where theory and observation agree or differ.

This first homework treats measurement as a form of reasoning rather than a plotting exercise. It also establishes a reusable experiment and reporting workflow for the rest of the course. It is intentionally guided because the first practice sessions begin after this deadline.

The Algorithmics timing experiment demo shows the measurement/reporting structure. You may use another programming language or environment, but your results must be reproducible.

Expected workload: approximately 7-9 hours for the five base tasks, including initial environment setup and concise reporting. This first set may take slightly longer than later sets because you are establishing a workflow that you can reuse. Bonus tasks are not included in this estimate.

General requirements

• Submit a report in PDF or HTML and submit the code/source files separately.
• The report must be readable without opening your notebook or following an external link.
• Use clear tables and plots. Label axes and include units.
• State the programming language, environment, input sizes, number of repetitions, and random seeds.
• Time only the operation being studied unless the task explicitly says otherwise.
• Aim for a concise report of approximately 3-5 pages, excluding code, raw measurement tables, and optional appendices.
• Acknowledge sources and substantial AI assistance. You remain responsible for every claim, result, and line of submitted code.

Base tasks

T1. Asymptotic winner versus practical winner (1p, conceptual)

Two libraries have the following documented processing costs for an input of size n >= 2:

T_A(n) = 0.3 * n * log2(n) milliseconds
T_B(n) = 5 * n milliseconds

Answer and justify:

• Which library is asymptotically better?
• Approximately where does the practical winner change?
• Which would you choose if n <= 100000? What about n = 10000000?
• How sensitive is the crossover to a 20% change in either leading constant?

Do not answer only with Big-O notation. Big-O suppresses the constants that determine this finite-size decision.

Next, construct your own two runtime functions U(n) and V(n) such that:

• U(n) is in Theta(n log n) and V(n) is in Theta(n);
• U(n) < V(n) for every integer 2 <= n <= 10**6;
• V(n) < U(n) for every n >= 10**8.

Give explicit positive constants and justify why both range conditions hold. The goal is to work backwards from a desired crossover, not merely copy the constants from the first example.

Deliverable: derivation of the supplied crossover, your constructed functions and inequality argument, a clearly scaled plot, and recommendations whose input ranges are explicit.

T2. From code to falsifiable predictions (1p)

Implement and test these three operations:

1. a linear scan that calculates the sum of absolute differences between consecutive values;
2. a library sorting method that returns a sorted copy;
3. a direct quadratic inversion counter: examine every pair of indices i < j and increase the count whenever a[i] > a[j]. For this experiment, use this Theta(n^2) method as the quadratic baseline; do not replace it with the faster merge-sort-based inversion counter.

For the linear scan and library sort, use random permutations at these five input sizes, spanning four orders of magnitude:

large_sizes = [100, 1_000, 10_000, 100_000, 1_000_000]

Use a fixed random seed and generate all inputs outside the measured region. The quadratic inversion counter must use a separate, smaller doubling sequence. Select at least five safe sizes after a short pilot run; do not attempt to run the quadratic method on one million values.

Before taking timing measurements:

• define the basic operation you count for each implementation;
• derive an exact operation-count formula for the linear scan;
• derive an exact comparison-count formula for the naive inversion counter;
• explain why an exact count cannot be inferred for the library sort without knowing its implementation and input behaviour;
• state a falsifiable prediction for each operation, including expected growth, a rough value for T(10n)/T(n) for the large-size sequence or T(2n)/T(n) for the quadratic sequence, and a result that you would regard as inconsistent with the prediction.

Create correctness tests, including a small inversion count calculated manually. Use fixed seeds and retain input generation outside the measured region.

Deliverable: implementations, correctness tests, exact counts/derivations where possible, and a compact prediction/experiment-design table written before the results.

T3. Infer growth from evidence (1p)

Measure the linear scan and library sort on all five specified large sizes. Measure the quadratic inversion counter on the safe doubling sequence selected in T2. Use at least seven trials per case and time.perf_counter() or an equivalent high-resolution monotonic clock. Keep every raw measurement.

For each operation:

• calculate observed T(10n)/T(n) ratios for the linear scan and sort, and doubling ratios for the quadratic counter;
• compare the normalised values T(n)/n, T(n)/(n*log2(n)), and T(n)/n**2;
• decide which normalisation, if any, becomes most stable for the larger inputs;
• calibrate the selected model on smaller inputs, predict one held-out larger measurement, and report prediction error; run the held-out case only if it is expected to finish within 30 seconds and fit comfortably in memory;
• explain timing noise, fixed overhead, or implementation effects when measured time does not follow the exact operation counts from T2.

Deliverable: raw data, a compact ratio/normalisation summary, held-out predictions, and at most 200 words deciding which growth claims are supported, contradicted, or still inconclusive.

T4. How input structure changes insertion sort (1p, conceptual/experimental)

Study insertion sort, whose work depends strongly on the input. Insertion sort maintains a sorted prefix: it takes the next value, shifts larger values one position to the right, and inserts the value into the resulting gap.

Use this working Python implementation or write an equivalent version in another language. It returns a sorted copy, the number of element comparisons, and the number of shifts. Boundary checks such as j >= 0 are not counted as element comparisons.

def insertion_sort_counted(values):
    a = list(values)
    comparisons = 0
    shifts = 0

    for i in range(1, len(a)):
        key = a[i]
        j = i - 1

        while j >= 0:
            comparisons += 1
            if a[j] <= key:
                break
            a[j + 1] = a[j]
            shifts += 1
            j -= 1

        a[j + 1] = key

    return a, comparisons, shifts


# Small correctness checks
for test in [[], [1], [3, 1, 2], [2, 2, 1], [5, 4, 3, 2, 1]]:
    result, comparisons, shifts = insertion_sort_counted(test)
    assert result == sorted(test)

Keep the input size fixed at n = 10_000 and use random seed 2026. Construct six datasets in total: four datasets for experiment A and two datasets for experiment B. Treat A and B as separate experiments with different controls; do not rank all six datasets against one another.

A. Ordering while keeping the same multiset

Start with the distinct values 0, ..., 9_999 and arrange them as:

1. a random permutation;
2. sorted order;
3. reverse-sorted order;
4. 100 consecutive sorted blocks of length 100, with the blocks placed in random order.

This keeps the multiset fixed, so ordering is the only experimental variable.

B. Frequency while keeping the same length and value domain

Generate two arrays of length 10,000 with values from 1, ..., 10_000:

1. independent uniform-category samples;
2. independent Zipf samples with s = 1.2, where the probability of rank r is proportional to 1/r**s.

Both arrays have length 10,000 and use the same allowed values, but they do not contain the same values with the same multiplicities. Uniform sampling should distribute observations relatively evenly, whereas Zipf sampling should repeat a few high-ranked values often. Report the actual number of distinct values in each generated array, for example with len(set(a)) in Python.

Before running the algorithms, record predictions separately for the two experiments:

• A: use the random permutation as the baseline. Predict whether sorted, reverse-sorted, and sorted-block input will require fewer, a similar number, or more element comparisons and shifts.
• B: use uniform sampling as the baseline. Predict whether Zipf sampling will require fewer, a similar number, or more element comparisons and shifts.

Exact counts are not expected. Give one brief reason for each prediction. Do not compare datasets from A with datasets from B.

For every dataset:

• verify correctness with assert result == sorted(data) or the equivalent library operation in your language;
• record insertion sort's element comparisons and shifts.

Run the counting experiment once on each fixed dataset. Timing is not required in T4.

Compare predictions with results, explain why insertion sort is sensitive to input order and repeated values, and distinguish the ordering experiment in A from the frequency experiment in B.

Deliverable: insertion-sort implementation and correctness tests; generator code and seed; one four-row table for A and one two-row table for B, each containing the predictions, distinct-value count, comparisons, and shifts; and at most 200 words of interpretation. No plot is required.

T5. Order and simplify typical CS growth functions (1p, conceptual)

Assume all logarithms are base 2 and n is sufficiently large. Order the following functions by asymptotic growth, grouping functions that belong to the same Theta class:

f1(n)  = log2(log2(n))
f2(n)  = log2(n)
f3(n)  = (log2(n))**3
f4(n)  = sqrt(n)
f5(n)  = n
f6(n)  = n*log2(n)
f7(n)  = n**2
f8(n)  = n**log2(n)
f9(n)  = 2**n

f10(n) = 2**log2(n)
f11(n) = n**(1 + 1/log2(n))
f12(n) = log2(n**n)

Your solution must:

• simplify f10, f11, and f12 algebraically before classifying them;
• group all Theta-equivalent functions;
• order the distinct equivalence classes;
• justify that every class is little-o of the following class;
• distinguish f(n) = Theta(g(n)) from asymptotic equivalence, which means f(n)/g(n) -> 1.

You may use the standard fact that for fixed positive constants a and b,

(log2(n))**a = o(n**b)

but explain how it applies. A numerical plot may support intuition but is not a proof.

Finally answer: if f(n) = Theta(g(n)), must f(n)/g(n) tend to 1? Give a counterexample from this task.

Deliverable: simplified forms, ordered equivalence classes, concise algebraic/limit arguments for every strict step, and the final counterexample.

Bonus tasks

B1. Construct incomparable monotone growth functions (bonus 1p)

Construct two positive, nondecreasing functions P(n) and Q(n) such that neither P(n) = O(Q(n)) nor Q(n) = O(P(n)).

Your construction must:

• define both functions unambiguously for every positive integer;
• prove that both functions are nondecreasing;
• identify one subsequence along which P(n)/Q(n) becomes arbitrarily large;
• identify another subsequence along which P(n)/Q(n) becomes arbitrarily small.

Hint: consider consecutive blocks of input sizes. On alternating blocks, allow one function to make a very large upward step while the other remains unchanged.

Deliverable: definitions, monotonicity arguments, the two subsequences, and a proof that neither Big-O relationship holds.

B2. Make a benchmark lie, then repair it (bonus 1p)

Using correct implementations and truthful measurements, construct two superficially reasonable benchmarking protocols that lead to opposite or substantially different conclusions about which method is better.

You may vary choices such as input range, input distribution, inclusion of setup costs, warm-up, repetition count, or summary statistic. Do not falsify or manually alter measurements.

Diagnose the validity problems. Then define a corrected protocol before running it, retain all raw measurements, and report the resulting conclusion.

Deliverable: both flawed protocols and results, diagnosis of at least three threats to validity, corrected protocol and results, and a short checklist that would prevent the errors.

Submission checklist

• The report contains the requested tables, plots, and short interpretations.
• The code runs from a clean start and includes correctness checks.
• Raw measurements are submitted as CSV or another simple tabular format.
• Report and code/source files are uploaded separately.
• File names follow the course naming convention, for example surname_HW01_report.pdf and surname_HW01_code.zip.