Skip to section
Foundationsfor rotation-free search
Section 6 of 5212% of course
Contents
Chapter 1 Section 1.6 65 min

Part I · Mathematical foundations

Chapter studio: make the notation yours

Practice indices, bounds, sums, coordinate products, and dot products cumulatively.

Studio protocol

Try working out each prompt on paper (or in a scratchpad) before clicking to reveal the solution. Recognizing an answer is a lot easier than generating it from scratch, but actually generating it is the only way to know if you've really internalized the notation.

Part A · positions and notation

1. Let r = [5, 9, −3, 8, 0]. State its length, final index, r₂, and r₄.

Length 5; final index 4; r₂ = −3; r₄ = 0.

2. A list has length D = 768. Write its valid index range.

Positions zero through 767; or written formally, 0 ≤ i < 768.

3. Explain the difference between v₂,₅ and v₅,₂.

The first picks outer list 2 and inner position 5. The second picks outer list 5 and inner position 2. Order definitely matters!

Part B · sums

4. Expand ∑ from i=2 through 5 of aᵢ.

a₂ + a₃ + a₄ + a₅.

5. Evaluate ∑ from i=0 through 3 of (2i−1).

The terms generated are −1, 1, 3, and 5; adding them up gives a sum of 8.

6. Write the sum of every entry in a length-D list.

∑i=0D−1 ai.

Part C · products

7. Find the coordinatewise-product of [2, 0, −3, 1] and [4, 5, 2, −6].

[8, 0, −6, −6].

8. Use that result to quickly compute their dot product.

8 + 0 − 6 − 6 = −4.

9. Find the bug here: ∑ from i=0 through D of aᵢbᵢ.

The upper bound should be D−1. Remember, index D doesn't exist in a list of length D!

10. Find the bug: ∑ aᵢbⱼ while i changes but j stays fixed.

This would just reuse one single coordinate of b over and over. A proper dot product needs aᵢbᵢ to keep the positions synced.

Part D · trace and justify

11. Try writing a loop invariant for a dot-product implementation.

Right before processing index i, the accumulator equals the sum from k=0 through i−1 of akbk. Because this stays true, after the final iteration it holds all D matching products.

12. Can nonzero lists have a dot product of zero? Give an example.

Absolutely. For example, [1,1] · [1,−1] = 1 − 1 = 0. The signed contributions perfectly cancel each other out.

13. Why is equal length a hard semantic requirement, and not just a coding convenience?

The definition explicitly pairs the value at every position of the first list with the value at that exact same position in the second list. If the lengths don't match, at least one position is left hanging without a defined partner.

14. A tiny list of length 1 contains just [−3]. What are its valid indices, and what is its self-dot-product?

Its only valid index is 0. Its self-dot-product is (−3)² = 9.

Capstone trace

Let's do one last full trace. Let a=[2,−1,3,0] and b=[4,5,−2,7]. Grab some paper and create columns for i, ai, bi, the product, and the running total. Your totals should progress exactly like this: 0 → 8 → 3 → −3 → −3. If your final answer is different, find the specific row where your trace diverges instead of just trying to redo the whole thing in your head.

Show me the capstone explanation

The coordinate products are 8, −5, −6, and 0. Adding them up gives a sum of −3. We needed four multiplications and three additions. Notice that the zero at a3 completely silences b3=7, but that position is still a crucial part of the shared shape of both lists.

Cumulative mastery check

Mastery 1 of 3

Which phrase fully defines a dot product?

Mastery 2 of 3

Which of these outputs remains a list?

Mastery 3 of 3

What's the best thing to do when a sigma notation feels confusing or opaque?

Chapter 1 complete

Great job! You now own the input language for Chapter 2

You can comfortably treat a mathematical list like an indexed array, read finite sums exactly like loops, align lists by index, and build up a dot product. Chapter 2 introduces a completely different multiplication rule—one that pairs every position with every other position. Take a breath, and let's dive in when you're ready.

Repository layer · second pass

Can you move among prose, notation, tables, and code without changing the operation?

Fluency means preserving meaning across representations. A row of aligned boxes, Σᵢaᵢbᵢ, a Python loop, and a table of contributions should all describe the same computation. If two forms disagree, one contains a bound, alignment, or accumulation error.

The studio is not a speed test. Work one representation at a time, predict the result, and then use another representation as an independent check. This habit becomes the verification strategy for the encrypted and hardware implementations later in the book.

Reasoning chain

  1. 1

    State the dimension and index range.

  2. 2

    Make alignment explicit.

  3. 3

    Write the expanded arithmetic.

  4. 4

    Compress it into notation.

  5. 5

    Implement it with assertions.

  6. 6

    Test zeros, negative values, repeated values, and a length mismatch.

Worked trace

Four views of one computation

  1. Choose A=[2,0,−1] and B=[3,5,4].
  2. The table gives products [6,0,−4].
  3. The sigma expression has indices 0 through 2.
  4. The loop accumulates 6, then 6, then 2.

Result. Every representation must produce the scalar 2.

Executable lens · Python

Make the hidden state visible

a, b = [2, 0, -1], [3, 5, 4]
trace, total = [], 0
for i in range(len(a)):
    contribution = a[i] * b[i]
    total += contribution
    trace.append((i, contribution, total))
assert (trace, total) == ([(0, 6, 6), (1, 0, 6), (2, -4, 2)], 2)

Retype this example, predict each intermediate value, and then change one input that touches a boundary.

Misconception clinic

Tempting mistakes

  • Checking only one friendly example.
  • Memorizing notation without being able to expand it.

Retrieval and transfer

Close the book first

  1. Create a five-coordinate example with exactly two zero contributions.
  2. Write a deliberate off-by-one bug, then explain which assertion catches it.
  3. Teach the difference between ⊙ and · in three sentences.