cs-134 — The Sliding Sensor Window

Problem

A weather station posts one reading per minute. The dashboard must flag any minute whose value exceeds the average of the previous three minutes (the three before it, not counting itself) by more than 10. Minutes with an incomplete window are never flagged.

Today's first twelve readings:

index:  0  1  2  3   4  5   6   7   8   9  10  11
value:  5  6  7  8  30  9  10  11  45  12  13  14

Two colleagues proposed implementations:

• Method A (nested re-sum): for each minute, add the previous three values again from scratch. Cost: k additions per minute (k = window).
• Method B (running sum): keep the window's sum; each step subtract the value leaving and add the value entering. Cost: O(1) per minute.

Your deliverables:

1. The flagged indices and values for the twelve readings, computed by hand (method A logic).
2. The per-minute cost of A and B, and the total operation count for a full day (n = 1440, k = 3) for each.
3. Which you would ship, and why — one sentence.
4. The input that breaks both methods, or makes their output undefined without an extra rule.

If the problem is ambiguous anywhere, state the assumption you are making and carry on — a stated assumption is part of a good answer.

Examples

• Input: the twelve readings, k = 3, threshold 10
• Output: flags at indices 4 and 8 (values 30 and 45) — day cost A: 4320 additions, B: 1440 updates

Solve for the worked instance first. Then ask what would change if one number, name, or condition were replaced by something stranger.

What to notice

• The two methods are not "slow vs fast" in the abstract: they compute the same flags, and the choice is justified by counted operations on the real n, not by a slogan.
• Method B's danger is state drift: one wrong subtraction corrupts every later flag — which is a correctness argument, not just style.
• A monitoring rule is only as defined as its boundary: the first three minutes and any window longer than the data need explicit decisions.

Discussion starter

After the solution is revealed, the class spends five minutes on this prompt: "The station upgrades to one reading per second (n = 86,400, k = 180). Re-count the operations. Does your ship decision change, and at what k would it flip?"

Constraints and assumptions

• Difficulty: Advanced (cost arithmetic feeding a design decision).
• Topics: algorithm selection, trade-offs, anomalies.
• "Previous three minutes" means exactly the three values before the current index — no wraparound, no missing-minute policy needed for this instance.
• Classroom-scale inputs unless the problem says otherwise.
• Time-box: about five minutes for a first attempt; partial answers with clear reasoning are worth more than silent struggling.
• Optional stretch (not required): describe an alternative approach and say when it beats the obvious one.

Hints and extension

• First nudge: which indices even have a full window?
• If stuck after three minutes, write the input/output line you expect and trace the smallest example by hand.
• After the reveal, attempt the extension below before the next lecture.
• Extension challenge: state the invariant of method B's running sum and the one-line test that would catch state drift in production.