Lecture 3: String Manipulation, Guess and Check, Approximations, Bisection

Lecture 3 has two halves that initially look unrelated. The first develops strings as sequences that can be measured, indexed, sliced, and traversed. The second compares algorithms for finding a cube root. Together, they teach the same deeper habit: define a search space, move through it systematically, and know exactly when to stop.

Dr. Ana Bell introduces three approaches to the same numerical problem: exhaustive guess and check, incremental approximation, and bisection search. Seeing them side by side makes the tradeoff between simplicity, accuracy, and speed concrete.

1. Strings are ordered sequences

A Python string is a case-sensitive sequence of characters. Letters, digits, punctuation, and spaces all count toward its length. The built-in len() function reports the number of characters.

course = "MIT 6.0001"

print(len(course))  # 10
print(course[0])    # M
print(course[-1])   # 1

Python uses zero-based indexing, so the first character is at index 0. Negative indexes count backward from the end: -1 selects the final character and -2 selects the character before it.

2. Slicing selects a range

Indexing returns one character. Slicing returns a substring and follows the pattern text[start:stop:step]. The start is included, the stop is excluded, and the default step is 1.

language = "PYTHON"

print(language[1:4])   # YTH
print(language[::2])   # PTO
print(language[::-1])  # NOHTYP
print(language[:3])    # PYT
print(language[3:])    # HON

The stop-exclusive rule is consistent with range(). A slice from 1 to 4 includes positions 1, 2, and 3. Once that rule is clear, even compact expressions such as text[::-1] become traceable rather than mysterious.

3. Strings are immutable

Immutability means an existing string object cannot be changed character by character. Assigning to word[0] causes a TypeError. To create a modified version, Python builds a new string and the variable is rebound to it.

word = "hello"

# word[0] = "y"  # TypeError: strings are immutable
word = "y" + word[1:]

print(word)  # yello

This distinction becomes more important later when the course introduces mutable objects. For now, the useful mental model is that string operations produce new values rather than editing the original object in place.

4. Loop directly over characters

A for loop can traverse the characters themselves. If the program only needs each character, direct iteration is clearer than generating indexes and then looking each one up.

phrase = "Bisection search"
vowel_count = 0

for character in phrase.lower():
    if character in "aeiou":
        vowel_count += 1

print(vowel_count)  # 6

This is an example of Pythonic code: the loop says what it means - for every character in the phrase - without adding an unnecessary counter. Index-based loops are still useful when the position matters, but direct iteration is the better default when only the values matter.

The in operator also treats a string as a sequence. The expression character in "aeiou" evaluates to a Boolean and lets the conditional read almost like English.

5. Guess and check: search every candidate

Guess and check, also called exhaustive enumeration, tries candidates systematically until it finds an exact answer or proves that the search space contains none. The approach works when candidates can be generated and each candidate can be checked.

cube = -125

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:", guess)  # -5

The loop stops as soon as the guess cubed reaches or passes the target. If it passes without matching, the number is not a perfect cube. Using abs(cube) creates a non-negative search space; the sign is restored after an exact root is found.

Exhaustive enumeration is easy to understand and can be perfectly adequate for a small space. Its weakness is that the amount of work grows with the size of the range.

6. Approximation: decide what “close enough” means

Many useful answers are not exact integers. An approximation algorithm starts with a guess, changes it by a small step, and stops when the error falls below a tolerance called epsilon.

cube = 10
epsilon = 0.01
step = 0.0001
guess = 0.0
number_of_guesses = 0

while abs(guess ** 3 - cube) >= epsilon and guess <= cube:
    guess += step
    number_of_guesses += 1

if abs(guess ** 3 - cube) < epsilon:
    print(guess, "is close to the cube root")
else:
    print("No answer found with this step and epsilon")

The algorithm exposes an important engineering tradeoff. A smaller step can produce a more precise result, but it requires more guesses. A larger epsilon accepts more error and may finish sooner.

The extra boundary condition matters. A step can jump completely over the narrow interval that counts as “close enough.” Without another reason to stop, the guesses may continue forever while the error grows. A reliable loop needs both a success condition and a failure boundary.

7. Bisection search: remove half the space

Bisection search is powerful when the search space is ordered and the check tells us whether the guess is too high or too low. Instead of advancing by a fixed step, the algorithm guesses the midpoint and discards the half that cannot contain the answer.

cube = 0.5
epsilon = 0.0001
low = 0.0
high = max(1.0, cube)
guess = (low + high) / 2.0
number_of_guesses = 0

while abs(guess ** 3 - cube) >= epsilon:
    if guess ** 3 < cube:
        low = guess
    else:
        high = guess

    guess = (low + high) / 2.0
    number_of_guesses += 1

print(guess, "is close to the cube root")

Each iteration preserves an interval that contains the answer. A low guess moves the lower boundary up; a high guess moves the upper boundary down. The next guess is always the midpoint of the smaller interval.

The initial boundaries must actually contain the answer. For a positive target below 1, its cube root is larger than the target, so using high = cube would exclude the solution. Setting high to max(1.0, cube) handles that case.

If the original search interval has size N, repeatedly halving it takes roughly log2(N) guesses to narrow it to one unit. This is why bisection scales much better than checking every candidate.

Practice lab

MIT's in-class questions emphasize tracing slices and following nested loops over strings. I used those themes, plus the lecture's cube-root algorithms, to build these original self-checks.

text = "ALGORITHM"
result = text[-1] + text[1:4] + text[::3]
print(result)

first = "code"
second = "debug"
matches = 0

for character in first:
    if character in second:
        matches += 1

print(matches)

name = "lance"
name[0] = "L"

Key takeaways

• Strings are ordered, case-sensitive sequences that support length checks, zero-based indexing, negative indexing, and slicing.
• A slice includes its start position, excludes its stop position, and can move forward or backward with a step.
• Strings are immutable; apparent modifications create new string objects.
• Directly iterating over characters is often clearer than looping over indexes.
• Guess and check systematically explores candidates and works well for small exact search spaces.
• Approximation introduces epsilon and step size, creating a tradeoff between accuracy and speed.
• A loop needs a safe failure boundary as well as a success condition.
• Bisection search uses ordering to remove half the remaining interval after every guess.
• Correct initial bounds are part of the algorithm; bisection cannot find an answer outside its interval.