MIT 6.0001 Lecture 3: String Manipulation, Guess-and-Check, Approximations, Bisection

Comprehensive review flashcards covering string manipulation, indexing and slicing, string immutability, loop paradigms, exhaustive enumeration, approximate solutions, and bisection search from 6.0001 Lecture 3.

How are strings conceptualized and compared in Python?

Strings are sequences of case-sensitive characters that can be compared using comparison operators such as ==, >, and <.

How does string indexing work in Python, and what are the index bounds?

Indexing starts at 0 for the first character and proceeds forward, while negative indexing starts at -1 for the last character. Attempting to access an index outside these bounds results in an error.

What is the general syntax for string slicing in Python, and what is the default step value?

The syntax is [start:stop:step]. If only two numbers are provided as [start:stop], the default step is 1.

What does the slice expression s[::-1] evaluate to?

It evaluates to the reversed string, equivalent to s[-1:-(len(s)+1):-1].

What does it mean that strings are "immutable" in Python?

It means string objects cannot be modified in place. An assignment like s[0] = 'y' causes an error, so modifications require creating a new string and binding the variable to that new object.

Why is iterating using "for char in s:" preferred over "for index in range(len(s)):"?

Iterating directly over the string with "for char in s:" is more "pythonic" and directly accesses each character without needing manual indexing.

What alternative name is given to the guess-and-check algorithm?

Exhaustive enumeration.

How does the guess-and-check (exhaustive enumeration) algorithm operate?

It systematically generates candidate solutions and checks whether each candidate solves the problem, continuing until a solution is found or all values have been tested.

In an approximate solution algorithm for cube roots, what condition stops the search for a "good enough" solution?

The search continues while $\lvert\text{guess}^3 - \text{cube}\rvert \ge \epsilon$, stopping when the difference is less than $\epsilon$.

In an approximate solution algorithm, what is the trade-off of decreasing the increment size?

Decreasing the increment size results in a slower program.

In an approximate solution algorithm, what is the trade-off of increasing epsilon ($\epsilon$)?

Increasing epsilon results in a less accurate answer.

How does bisection search choose its next guess at each step?

It cuts the search interval in half each iteration by selecting a new guess halfway between the current low and high bounds: (high + low) / 2.0.

What is the size of the search space on the kth guess in bisection search?

$$\frac{N}{2^k}$$

On what order of steps does bisection search converge?

It converges on the order of $\log_2(N)$ steps.

Under what condition does bisection search work?

It works when the value of the function varies monotonically with the input.

Why does a bisection search using an initial range of 0 to x fail to find the cube root when $x < 1$?

Because when $x < 1$, the cube root is actually greater than $x$ and less than 1, meaning the solution lies outside the [0, x] search interval.