Week 14 — From a correct algorithm to a convincing report

The big question

How do we recommend an approach using correct outputs, a cost argument, and honest measurements together? The final week combines the course's habits. Define the question, inspect the repeated operation, improve the method, check the answer, measure fairly, and explain when the improvement matters.

Your outcomes are to compare two complete approaches, include setup that belongs to the algorithm, use four input sizes and repeated timings, calculate ratios and a prediction, and state a recommendation with limitations. The project is an explanation of your reasoning, not a contest for the largest speedup.

Türkçe: Son hafta yalnızca hızlı bir program yazma haftası değildir. Aynı soruya doğru cevap veren iki yöntemi karşılaştırıyoruz. Neden farklı büyüdüklerini hesaplıyor, sürelerle kontrol ediyor ve hangi koşullarda hangisini seçeceğimizi anlatıyoruz. Büyük bir hızlanma sayısı, eksik bir deneyin yerini tutmaz.

Prerequisite warm-up, with answers

There are n orders and m watched customer names. What is the worst-case membership work if every order scans the watch list? What changes if we build a set once? What if m remains fixed at ten while n grows?

Answers: Scanning costs O(nm). Set preparation plus the scan costs O(n + m) on average, assuming ordinary hash behavior and simple keys. If m grows proportionally with n, the slow method is quadratic in n. If m stays ten, 10n is linear in n. A multiplication involving two symbols is not automatically quadratic in either one separately.

If measured time rises from 0.10 to 0.40 seconds when input doubles, the ratio is 0.40 / 0.10 = 4. This supports a quadratic-dominant model over the tested range. It does not prove that every future input or every different input arrangement follows that model.

Worked example 1 — The watched-customer report

Use the lesson's problem: total spending for customers appearing on a watch list. Make the output contract explicit. Amounts are nonnegative integer cents. Every order contributes once if its customer is watched. Repeated watch-list names do not multiply spending. Return totals for watched customers who actually have orders; omit watched names with no orders.

Watch list: ["Ada", "Cem"]. Orders arrive as Ada: 300, Ece: 900, Cem: 200, Ada: 450 cents.

The output is {"Ada": 750, "Cem": 200} cents. Its total 950 equals the included order amounts 300 + 200 + 450. The excluded 900 must not appear. Integer cents keep this example's arithmetic exact.

Approach A scans the watch list inside the order loop. Approach B constructs a set of watched names once, then uses it for membership. Both update a dictionary of totals. Their correctness comes from the same invariant: after processing the first k orders, each stored total equals that customer's eligible spending in those k orders. The next order either changes no total or adds its amount to exactly the correct total.

Set construction preserves this contract because the contract asks whether a name is watched, not how many times it occurs in the watch list. The set is used for lookup; we do not iterate over it to determine report order.

Türkçe: İlk k sipariş işlendiğinde toplamların ne anlama geldiğini söyleyebilmek önemlidir. Yeni sipariş geldiğinde bu anlamın bozulmadığını gösteririz. Bu bir doğruluk gerekçesidir. İki programın bir örnekte aynı sonucu vermesi ise bu gerekçeyi destekleyen bir testtir; bütün olası girdiler için tek başına kanıt değildir.

A complete, bounded four-size benchmark

This independent example implements both methods and checks small edge cases. It then uses four doubling sizes, three repeats, and the best time. Input generation is deterministic; timings will vary. The slow method's watch list grows with n. Setup outside the timer creates shared input; the fast method's required set construction stays inside its timed function.

Read the block in these stages; you do not need to understand every line simultaneously.

Each generated customer appears in two orders, and one fifth of the customer names are watched. Thus both hits and misses occur while n and m grow together. This is a specified workload, not a random sample of all possible order patterns.

from time import perf_counter

def summarise_slow(orders, watch):
    totals = {}
    for name, cents in orders:
        if name in watch:
            totals[name] = totals.get(name, 0) + cents
    return totals

def summarise_fast(orders, watch):
    watched = set(watch)
    totals = {}
    for name, cents in orders:
        if name in watched:
            totals[name] = totals.get(name, 0) + cents
    return totals

cases = [
    ([], ["Ada"], {}),
    ([("Ece", 900)], ["Ada"], {}),
    ([("Ada", 300), ("Ada", 450)], ["Ada", "Ada"], {"Ada": 750}),
    ([("Ada", 300), ("Ece", 900), ("Cem", 200), ("Ada", 450)],
     ["Ada", "Cem"], {"Ada": 750, "Cem": 200}),
]
for orders, watch, expected in cases:
    assert summarise_slow(orders, watch) == expected
    assert summarise_fast(orders, watch) == expected

previous = None
for n in [200, 400, 800, 1600]:
    names = [f"customer{i}" for i in range(n // 2)]
    orders = [(names[i % len(names)], 10 + i % 91) for i in range(n)]
    watch = names[:n // 10]
    expected = summarise_slow(orders, watch)
    assert summarise_fast(orders, watch) == expected
    samples = {"slow": [], "fast": []}
    functions = [("slow", summarise_slow), ("fast", summarise_fast)]
    for repeat in range(3):
        order = functions if repeat % 2 == 0 else functions[::-1]
        for label, function in order:
            start = perf_counter()
            result = function(orders, watch)
            elapsed = perf_counter() - start
            samples[label].append(elapsed)
            assert result == expected
    slow = min(samples["slow"])
    fast = min(samples["fast"])
    ratios = ("first size" if previous is None else
              f"doubling: slow={slow / previous[0]:.2f}, fast={fast / previous[1]:.2f}")
    print(f"n={n}, m={len(watch)}, slow={slow:.6f}s, fast={fast:.6f}s; {ratios}")
    previous = (slow, fast)

The functions do not mutate the supplied lists, so reusing them is fair. Both create a fresh result on every call. Checks and printing occur outside timing. Alternating execution order reduces a simple “always run A first” bias; it does not eliminate all environmental variation. These small sizes keep the example safe to run. If the fastest measurements are too short to be stable, increase sizes carefully or repeat a clearly defined batch.

A plot belongs in the final notebook: input size n on the horizontal axis, seconds on the vertical axis, both logarithmic, and a labelled line for each approach. Use the actual recorded times, with the repeat summary stated. Do not substitute the illustrative numbers below for your own measurements.

Worked example 2 — Interpret a table and make a prediction

The following numbers are invented teaching data, chosen to make the arithmetic visible. They are not results from the preceding code.

For the last row, A's growth ratio is 1.280 / 0.320 = 4. B's is 0.016 / 0.008 = 2. Speedup compares the methods at the same n: 1.280 / 0.016 = 80. A growth ratio and a speedup ratio answer different questions.

Assuming the same dominant behavior at n = 16,000, predict 1.280 × 4 = 5.120 seconds for A and 0.016 × 2 = 0.032 seconds for B. Predicted speedup is 5.120 / 0.032 = 160. Mark these values as predictions, not extra measured rows.

The operation analysis explains the table: here m grows with n, so A's O(nm) becomes O(n²); B's average O(n + m) becomes O(n). The measurement is consistent with that reasoning. It does not establish hash worst cases, memory limits, or behavior under different customer distributions.

Türkçe: Aynı satırdaki iki süreyi bölersek yöntemler arasındaki hızlanmayı buluruz. Aynı sütundaki ardışık süreleri bölersek girdinin büyümesine verilen tepkiyi buluruz. Bu iki oranı karıştırmamak, rapordaki en önemli hesap alışkanlıklarından biridir.

Three graduated practice problems

Problem 1 — Repair the report total

A report collects r matching orders, then repeats total += sum(all_matching_values) once per matching order. For values [10, 20, 30], find the returned total, the intended total, and an efficient repair. Also replace repeated list concatenation and define the report text's separator policy.

Solution 1 — Fix meaning before speed

The sum is 10 + 20 + 30 = 60. Repeating it three times gives 60 + 60 + 60 = 180, so the program returns three times the intended total. In general it returns r times the sum and spends O(r²) time recomputing it.

Filter eligible orders with a set prepared once. Append each eligible order to the output list. Compute the sum once, or maintain a running total as orders are appended. The total is now 60. For report text, specify comma-space separators with no trailing separator and join the identifiers once. This deliberately defines the required formatting; a version ending with an extra comma is not an identical string. With n orders, m watched names, and L output characters, average time is O(n + m + L), with storage for the set and output.

Problem 2 — Two numbers, two positions

Decide whether two different positions contain values adding to a target. Explain the result for [3] with target six and [3, 3] with target six. Give a linear-average-time method.

Solution 2 — Check earlier values before storing this one

def has_pair(data, target):
    seen = set()
    for value in data:
        if target - value in seen:
            return True
        seen.add(value)
    return False

assert has_pair([3], 6) is False
assert has_pair([3, 3], 6) is True
assert has_pair([4, 7, 1], 8) is True
assert has_pair([], 8) is False

For the first 3, the required partner is 6 − 3 = 3, but seen is empty. Store 3 only after checking. A second 3 then finds a partner from a different position. The one-element list cannot reuse its sole position. For [4, 7, 1], needed partners are 4, then 1, then 7; the third item finds the earlier 7. There are at most n lookups and n insertions: O(n) average time and O(n) worst-case extra space. A fair all-pairs baseline checks index pairs i < j and may require n(n − 1)/2 sums when no pair exists.

Problem 3 — Audit a performance claim

A draft says “B is 100× faster, therefore it is proven O(n).” It times A on reverse-sorted values, B on sorted values, excludes B's required preprocessing, and presents only one size. Give a complete repair plan.

Solution 3 — Make the claim testable

First specify one output contract and test both implementations against expected answers, including empty, repeated, and missing cases where relevant. Give both identical data at each size. Include required preprocessing in end-to-end time, or label a separate query-only measurement and report preparation separately. Use four sizes and at least three repeats, with the chosen summary stated. Record both growth ratios and same-size speedups. Explain the operation count independently, then make a conditional prediction. Replace “proven” with a statement that measurements support the proposed model over the tested range, followed by its limitations.

The existing final project, made manageable

For an optional, ungraded portfolio, the lesson suggests one notebook AA_Final_YourName.ipynb, a report of about two pages, and a five-minute presentation. The notebook contains both approaches, the benchmark with at least three repeats, and a labelled log–log figure. The presentation uses the problem, one figure, one recommendation, and one limitation, without code on the slides. No project submission is required; only the midterm (50%) and final (50%) contribute to the grade.

Use the original seven-part report structure. A practical two-page allocation follows; it is writing guidance, not a new rubric.

Put framing and methods on approximately the first page, then evidence and decisions on the second. Keep full implementations and raw measurements in the notebook. The ungraded checklist covers framing, two correct approaches, analysis, benchmark quality, interpretation/prediction, recommendation and limitations. A small well-supported improvement can satisfy this reasoning-focused standard.

Misconceptions, glossary, and final readiness

Profiling identifies where time is spent; it does not itself prove complexity. cProfile reports function-level costs, not a precise per-source-line breakdown of a membership expression. Use section timings and focused comparisons to investigate a suspected operation. The “90/10 rule” is a heuristic, not a measured guarantee for every program.

Repeatedly sorting n items n times can be O(n² log n), so not every hidden expensive operation is exactly quadratic. String concatenation may be optimized in some interpreter contexts; report what actually happens. The optional chapter puzzles extend these reasoning habits, but they are not extra final-project deliverables.

You are ready to finish when another person can reproduce your table, understand why both methods answer the same question, follow your prediction arithmetic, and identify the scope of your recommendation. Repair missing correctness with a hand-traced example. Repair unclear growth by exposing the repeated operation and its bound. Repair a weak report by replacing “much faster” with a size, a ratio, an explanation, and a limitation.

Türkçe: Son kontrol şudur: Arkadaşınız sonuçları sizin yardımınız olmadan anlayabiliyor mu? Hangi sayı ölçüldü, hangisi hesaplandı, hangi varsayım kullanıldı açık mı? Bu açıklık, sonraki Veri Yapıları ve Algoritmalar dersine taşıyacağınız temel beceridir.

Make the same sensor report in two ways

For each sensor, report how many accepted readings it has and their mean (average). Both methods must reject the same invalid rows and use the same rule when no readings exist. This example also appears in CP1, but you do not need that course to follow it.

Draw or trace. Use valid rows T1=10, T1=20, T2=30 and a rejected T1=missing row. Draw repeated per-sensor scans beside one pass updating a dictionary of count and sum.

Predict before checking. For n accepted rows and k requested sensors, which route checks the same rows again? What must be included if the sensor names are not supplied?

Worked reasoning

With n accepted rows and k supplied sensor names, scanning every row for each sensor takes O(kn) work, assuming constant-time comparisons. A dictionary can collect counts and totals in one pass: expected O(n) time, then O(k) to report the answers, using O(k) extra storage for those sensors under the usual hashing assumptions. If k is fixed, both methods grow linearly with n. The first becomes quadratic when k grows in proportion to n. Finding sensor names or sorting the report adds work if required. Time the same complete task in both methods.

rows = [("T1", 10.0), ("T1", 20.0), ("T2", 30.0)]  # already validated
sensors = ["T1", "T2", "T3"]
scanned = {}
for sensor in sensors:
    readings = [value for name, value in rows if name == sensor]
    scanned[sensor] = (len(readings), sum(readings) / len(readings) if readings else None)

aggregates = {sensor: [0, 0.0] for sensor in sensors}
for sensor, value in rows:
    aggregates[sensor][0] += 1
    aggregates[sensor][1] += value
single_pass = {sensor: (count, total / count if count else None)
               for sensor, (count, total) in aggregates.items()}
assert scanned == single_pass == {"T1": (2, 15.0), "T2": (1, 30.0), "T3": (0, None)}
print(single_pass)

Change one thing. Add duplicate observations, a sensor with no valid readings and more different sensors. Defend which changes affect correctness, operation counts and memory. This is an optional capstone context, not a prerequisite to have taken CP1.

Türkçe: Aynı geçerli satırları ve çıktı kuralını koru. k sabitse kn doğrusal büyür; k de büyüdüğünde ayrı değişken olarak izlenmelidir.

Additional analysis laboratory

The final report should read like an engineering decision, not a speed contest. It must connect correctness, model, measurement, and limitation.

Extra exam-style prompt: Method B is faster at four sizes but uses extra memory and changes output order. Can the report recommend it?

Solution: Only if the output contract permits the changed order and the memory cost is acceptable. If order must be preserved, Method B must be repaired or rejected despite the timing. If order is irrelevant, the report can recommend B for the tested workload while stating the memory trade-off and the tested size range.

Turkce: Final proje "en hizli kodu buldum" demek degildir. Dogru cevap, maliyet modeli, olcum siniri ve hangi kosulda onerildigi ayni paragrafta gorunmelidir.