2026-01-06Hung-Chih Hsueh

MIT 6.100L: Loops, Guessing, and Binary

Study notes for MIT OpenCourseWare 6.100L Lecture 4, covering string loops, exhaustive enumeration, approximation, bisection search, and binary.

These notes are based on the MIT OpenCourseWare 6.100L Fall 2022 Lecture 4 slides, course page, and corresponding YouTube video. The content intentionally uses “stories + small programs” to make concepts stick, so when you see loops, you won’t just think of range(10).

0. The Main Theme: Three Ways Iteration Shows Up

Lecture 4 looks at loops through three different lenses:

Traversing sequences (strings are sequences too): Scanning character by character, making decisions one at a time (Loops over Strings).
Brute-force but guaranteed search (exhaustive enumeration / guess-and-check): When the solution space is enumerable, just guess one by one until you find it.
Understanding how machines store numbers (binary & floating point): The 0.1 you think you’re using isn’t actually the 0.1 you think it is.

1. Loops over Strings: You’re Not “Running Through a String,” You’re “Patrolling a Street”

Many people get stuck on their first loop wondering, “What exactly am I iterating over?” Think of it this way: If you have something that can be traversed in order (a sequence), you can process its elements one by one.

Strings are sequences, so the concept applies.

1.1 Three Common Approaches: Indexing, Characters, or Membership Testing

A) Using indices (useful when you need positions)

s = "banana"
for i in range(len(s)):
    print(i, s[i])

B) Iterating directly over characters (most intuitive, hardest to mess up)

s = "banana"
for ch in s:
    print(ch)

C) Using membership (like being a gatekeeper)

vowels = "aeiou"
s = "banana"

count = 0
for ch in s:
    if ch in vowels:
        count += 1

print("vowels:", count)

Key concept: in for strings means “does it contain this character/substring”; you’re not comparing sizes, you’re asking: “Are you one of us?”

2. Example: Robot Cheerleaders — Using String Loops for “Linguistic Fine-Tuning”

This example is quite fun: you want robots to chant, but you need to handle a/an correctly:

a: before consonant sounds (e.g., a ball)
an: before vowel sounds (e.g., an apple)

We’ll use a simplified rule: Use an for letters A/E/F/H/I/L/M/N/O/R/S/X (commonly pronounced starting with a vowel sound).

def cheer(word: str) -> None:
    an_letters = set("aefhilmnorsx")  # simplified demo only
    for ch in word.lower():
        article = "an" if ch in an_letters else "a"
        print(f"Give me {article} {ch}!")
    print("What does that spell?")
    print(word.upper() + "!!!")

cheer("MIT")

You’ll see: even though we’re “looping through a string,” what we’re actually doing is classifying each character + controlling output format. This is the most common pattern for string loops: scan, decide, accumulate/output.

3. Finger Exercise: Cube Root of N (only for perfect cubes)

The MIT OCW Lecture 4 Finger Exercise asks: given a positive integer N, find its integer cube root; if it’s not a perfect cube, output error.

The “key pattern” here is: you must know when to stop. Since guess-and-check can’t test infinitely many values, you need a “stopping condition.”

3.1 Solution (brute-force but reliable)

def cube_root_or_error(N: int) -> None:
    guess = 0
    while guess**3 < N:
        guess += 1

    if guess**3 == N:
        print(guess)
    else:
        print("error")

cube_root_or_error(27)  # 3
cube_root_or_error(28)  # error

4. Guess-and-Check: Brute Force Isn’t a Sin, Not Having a Stopping Condition Is

Guess-and-check (also called exhaustive enumeration) has a philosophical flavor: If you can enumerate all possible answers, you’ll eventually find the answer. But the prerequisite is that you must be able to stop.

4.1 Example: Square root (only for perfect squares)

x = int(input("Enter an integer: "))
guess = 0

while guess**2 < x:
    guess += 1

if guess**2 == x:
    print("Square root of", x, "is", guess)
else:
    print(x, "is not a perfect square")

What about negative numbers?

The slides also remind us: if x is negative, guess**2 < x will be False from the start (left side ≥ 0, right side < 0), the loop won’t run, and you’ll get “not a perfect square,” but the message isn’t user-friendly. You can use a sign flag first, or convert to positive (depending on the problem requirements).

5. `break`: The Emergency Exit for Loops (But Don’t Become Dependent on It)

Sometimes you already know “running more is pointless,” so you should stop. break will terminate the innermost for/while, jumping out of the loop immediately.

5.1 Cube root: Slightly faster version (break when exceeded)

cube = int(input("Enter an integer: "))

for guess in range(abs(cube) + 1):
    if guess**3 >= abs(cube):
        break

if guess**3 != abs(cube):
    print(cube, "is not a perfect cube")
else:
    if cube < 0:
        guess = -guess
    print("Cube root of " + str(cube) + " is " + str(guess))

Two key points here:

Early stopping: Once guess**3 >= abs(cube), you know later values are even less likely to match, so stop immediately.
Convert negative to positive, then restore the sign at the end: Cleaner flow.

5.2 `for-else` (easily misunderstood but powerful)

Python’s for/while can be paired with else: The else block executes only if the loop “completes normally” without being interrupted by break.

This semantics is perfect for “did the search fail” scenarios:

secret = 7

for i in range(1, 11):
    if i == secret:
        print("yes, it's", i)
        break
else:
    print("not found")

Think of else as: “I really went through every possibility, and still didn’t find it.”

6. Boolean Flag: Using Booleans as Signal Lights (found / not found)

If you don’t want to use for-else, you can use a Boolean flag: “Turn on the light (True) when found, keep it off (False) when not found,” then act based on the light’s state at the end.

secret = 7
found = False

for i in range(1, 11):
    if i == secret:
        print("yes, it's", i)
        found = True

if not found:
    print("not found")

This pattern is especially useful when “you need to do more things later,” for example: after finding something, you need to record more information, or pass state across multiple code sections.

7. Childhood Trauma Returns: Solving Word Problems with Loops (But Watch the Performance)

The slides use a ticket-selling word problem as a demo: Alyssa, Ben, and Cindy’s ticket sales satisfy certain relationships, the total is fixed, find Alyssa’s sales.

7.1 Small numbers: Three nested loops work (but slow)

for alyssa in range(11):
    for ben in range(11):
        for cindy in range(11):
            total = (alyssa + ben + cindy == 10)
            two_less = (ben == alyssa - 2)
            twice = (cindy == 2 * alyssa)

            if total and two_less and twice:
                print(f"Alyssa sold {alyssa} tickets")
                print(f"Ben sold {ben} tickets")
                print(f"Cindy sold {cindy} tickets")

7.2 Large numbers: Reduce unknowns (dimension reduction)

When numbers become 1000 and differences become 20, three nested loops become very slow. A better approach: loop over only one variable, calculate the others directly from equations.

for alyssa in range(1001):
    ben = max(alyssa - 20, 0)
    cindy = alyssa * 2
    if alyssa + ben + cindy == 1000:
        print("Alyssa sold " + str(alyssa) + " tickets")
        print("Ben sold " + str(ben) + " tickets")
        print("Cindy sold " + str(cindy) + " tickets")

The “big idea” here is: use computation to simplify the problem structure. Not every problem should be brute-forced with three nested loops.

8. Binary and Floating Point: You Think You’re Computing 0.1, But You’re Actually Computing “Some Binary Fraction Closest to 0.1”

Lecture 4 uses a short code snippet as a “psychological shock”:

x = 0
for i in range(10):
    x += 0.1

print(x == 1)
print(x, "==", 10 * 0.1)

Sometimes you’ll see x == 1 is False. It’s not Python acting up—it’s that binary floating point cannot precisely represent most decimal fractions.

8.1 Core Reason (ultra-condensed version)

Computer hardware uses 0/1 states to represent information; binary is hardware-friendly.
But decimal 1/10 (i.e., 0.1) is an infinitely repeating fraction in binary, so it can only be approximated.
Approximations accumulate over many operations, potentially causing comparison results to differ.

8.2 Practical Advice: Don’t Use `==` to Compare Floats

Use “tolerance” comparison instead:

def is_close(a: float, b: float, eps: float = 1e-10) -> bool:
    return abs(a - b) < eps

x = 0.0
for _ in range(10):
    x += 0.1

print(is_close(x, 1.0))  # True (usually)

9. Converting Decimal Integers to Binary: Use `% 2` to Get the Last Bit, Use `// 2` to Right-Shift

This is your first clear look at “implementing a conversion algorithm with a loop.”

The idea:

x % 2 gives you the last bit (0 or 1)
x // 2 divides the integer by 2 (equivalent to a binary right-shift by one)
Repeat until x becomes 0
Note: you get bits from right to left, so you need to reverse or build the string in reverse order.

def dec_to_bin(n: int) -> str:
    if n == 0:
        return "0"

    is_neg = n < 0
    n = abs(n)

    bits = ""
    while n > 0:
        bits = str(n % 2) + bits
        n //= 2

    return "-" + bits if is_neg else bits

print(dec_to_bin(19))   # 10011
print(dec_to_bin(1507)) # 10111100011

10. Wrap-Up: The Skills This Lecture Really Wants You to Take Away

You didn’t learn “for/while syntax,” you learned three reusable patterns:

Scan: Look at data character by character, element by element
Search: Enumerate candidate answers, filter with conditions
Transform: Convert data from one representation to another

Once you have these three patterns in your head, loops are no longer just “repeating something”—they become your problem-solving engine.