Lecture notes · Programming in Python · Lecture 4

Loops over Strings, Guess-and-Check, and Binary

MIT 6.100L Intro to CS and Programming using Python, lecture 4, explained in plain English

Want this lecture to stick? In LessonBound you get checked practice questions for every part, can ask about anything you don't get, and can listen with your screen off. Free, no ads.

Learn this lecture free

Watch or read the original lecture: MIT OpenCourseWare.

Part 1 · 0:00–10:00

This part explains how loops can stop early with a break statement, and it starts a small coding exercise that counts even numbers using a loop.

Key ideas

A loop repeats lines of code automatically. A while loop repeats as long as a condition is true, and a for loop repeats once for each value in a sequence. 0:34
A for loop's sequence of values does not have to be numbers. It can also be non-numerical. 1:17
A break statement stops the loop that immediately surrounds it, right away. Any lines after the break inside that loop are skipped. 1:39
To count how many numbers in a range are even, check whether the remainder when dividing by 2 is 0. Each time that is true, add 1 to a counter. 8:00
Set the counter to 0 before the loop starts. The loop variable i then takes each value in turn, so the loop does the counting for you. 8:52

Words to know

break statement: A command that makes the program leave a loop early, before the loop would normally end.
condition: A yes-or-no test in the code. A while loop keeps going as long as its condition is true.
nested loop: A loop placed inside another loop, so the inner loop runs again each time the outer loop runs.
remainder: What is left over after dividing one number by another. For example, 5 divided by 2 leaves a remainder of 1.

Example

Imagine you are checking a long list of names for one particular name. Once you find it, you stop reading the list and put it down. A break statement works the same way: it stops the loop as soon as the job is done, and the rest of the list is never checked.

3 checked practice questions for this part are in the app.

Part 2 · 10:00–20:00

This part shows how a for loop can go through the letters of a word directly, and how a short cheerleader program uses two loops together.

Key ideas

A for loop can count from 0 up to the length of a string. Each number is then used as an index to look up one letter. This works, but it takes extra steps to read. 11:08
A string is a sequence of characters, so a for loop can go through the letters themselves, one at a time. You no longer need the index as a middleman. 13:22
The keyword 'in' checks whether a character is part of a group of characters. This is much shorter than writing many 'or' checks, such as checking every digit from 0 to 9. 14:45
The cheerleader program uses two separate loops. The first loop spells the word one letter at a time, and the second loop repeats the word a set number of times. 17:24
When spelling, the program picks 'an' or 'a' before each letter based on how the letter sounds in English. An if/else statement makes that choice. 18:30

Words to know

index: The position number of an item in a sequence. In a string, the first letter is at index 0.
loop variable: The name you give to the value a for loop holds on each pass through the loop. You can pick any name you like.
case sensitive: Capital and lowercase letters count as different. So a lowercase 'd' is not the same as a capital 'D'.
f-string: A way to put a variable's value into a line of printed text, using an f in front of the quotation marks. It was covered in lecture 2.

Example

Imagine a teacher calling the roll. She could say 'student number 1, student number 2,' then look up each name. Or she could just read each name straight from the list. The second way is shorter and easier to follow, just like looping over the letters directly.

3 checked practice questions for this part are in the app.

Part 3 · 20:00–30:00

This part shows how a loop can repeat a task a set number of times, and how to count unique letters in a string by keeping a record of letters already seen.

Key ideas

A for loop with range(times) runs exactly that many times, counting from 0 up to times minus 1. The loop variable changes on each pass, but you don't have to use it. 20:18
To count unique letters, keep a second variable, a string called seen, that holds every letter you have already found. 22:48
Check whether each letter is already in seen. If it is not, add it to seen. If it is, do nothing, so repeated letters are not counted twice. 24:42
Once seen holds one copy of each letter, its length is the number of unique letters, so you don't need a separate counter. 29:12
The if statement has no else part because there is nothing to do when a letter has already been seen. 29:40

Words to know

loop variable: The variable, like i in a for loop, that takes a new value each time the loop repeats.
Boolean: A value or expression that is either true or false. The word not flips a Boolean, so true becomes false and false becomes true.
append: To add one new item to the end of a list or string.
pass: A line of code that does nothing. It is used when a branch of an if statement should be left empty.

Example

Think of a guest list at a party where you only want each name written down once. Before you write a name, you check the list. If the name is already there, you skip it. If not, you add it. When you finish, the number of names on the list is the number of different guests.

3 checked practice questions for this part are in the app.

Part 4 · 30:00–40:00

This part teaches guess-and-check, a simple method that tries every possible answer in order until it finds the right one or runs out of options.

Key ideas

Guess-and-check (also called exhaustive enumeration) means you make a guess, test whether it solves the problem, and keep guessing until you find an answer or run out of options. Failing to find one does not prove that no answer exists. 33:03
Guessing at random wastes time. Counting up in a fixed pattern, starting from 0, lets the computer check every possibility quickly and in order. 34:29
The loop needs a stopping rule. For a number x, you stop once your guess squared is bigger than x, because every bigger guess would also be too big. 35:56
After the loop ends, an if/else checks why it stopped. If guess squared equals x, the number is a perfect square. If not, it is not a perfect square. 38:27
This method does not work for negative numbers. The loop never starts, because 0 squared is not less than a negative number. 39:30

Words to know

exhaustive enumeration: Trying every possible answer, one at a time, until you find the right one or have tried them all.
infinite loop: A loop that never stops because its stopping condition is never met. It can freeze a program.
perfect square: A number you get by multiplying a whole number by itself, such as 4 (2 times 2) or 9 (3 times 3).
keyword: A word that Python reserves for its own use, such as pass or while. You cannot use it as a variable name.

Example

Imagine you are looking for a friend's house on a street by checking house numbers one at a time, starting from the lowest. If you reach a number higher than the one you want, you know the house is not on this street, so you can stop searching. The stopping point saves you from checking every house on the map.

3 checked practice questions for this part are in the app.

Part 5 · 40:00–50:00

This part shows how to check values one by one with a loop, and how to use a true-or-false flag to remember what happened and act on it at the end.

Key ideas

Guess-and-check tries values one at a time. We have to stop at some point because we cannot test an infinite number of values. 43:17
A flag is a variable that is either true or false. We start it at false, change it to true only when something special happens, and then check it at the end. 40:42
For a negative input, the code sets the flag to true and then asks the user if they meant the positive number. Otherwise the flag stays false. 41:05
A for loop fits guess-and-check well because it goes through a fixed set of values in order and stops when they run out. 43:37
If you print 'not found' inside the loop, it prints once for every wrong number. To print it only once, wait until the loop is finished, or use a found flag. 49:19

Words to know

flag: A variable that holds either true or false, used to remember whether something happened.
Boolean: A word for a value that is either true or false, and the kind of value a flag holds.
for loop: A loop that goes through a list of values in order, one at a time, and then stops by itself.
break: A command that stops a loop right away, even if it has more values to go through.

Example

Think of a teacher calling names from a class list to find one student. The teacher goes down the list in order, and when the name is found, they stop calling. If they reach the end without finding it, they announce 'not found' once, not after every name.

3 checked practice questions for this part are in the app.

Part 6 · 50:00–1:00:00

This part shows how to use true-or-false flags to track events in a loop, and how a for loop can solve a cube root problem by checking every possible guess.

Key ideas

A Boolean flag is a variable that starts as false and changes to true when an event happens, so you can check later whether that event happened. 50:18
The 'not found' message goes after the loop, not inside it, because it only needs to print once. An else inside the loop would print a message on every wrong guess. 53:31
A Boolean variable can only be in one of two states, such as true or false, or 0 or 1. The programmer must remember which values mean which state. 54:35
The cube root code uses a for loop to try every whole number from 0 up to the number plus 1, checking whether each one's cube matches. For negative inputs, it works with the positive version and then adds the minus sign back. 56:23
The code can stop early with break once a guess's cube is equal to or greater than the target, because larger guesses cannot match. After stopping, it checks why the loop ended. 58:33

Words to know

Boolean flag: A variable that is either true or false (or 0 or 1) and changes when something happens in the code, so you can check later whether it happened.
Guess-and-check: A method where you try possible answers one at a time until you find the right one.
Absolute value: A number's size without its sign. For example, the absolute value of -5 is 5.
Break: A command that stops a loop right away, even if it has not finished going through all its values.

Example

A teacher checks a class roster by writing 'absent' next to every name at the start. When a student answers, the teacher changes that name to 'present.' At the end, the teacher reads out only the names still marked absent, instead of making an announcement after every name.

3 checked practice questions for this part are in the app.

Part 7 · 1:00:00–1:13:09

This part shows how a computer can solve puzzles by trying values, why it stores decimal numbers in a way that can cause tiny errors, and how binary numbers work.

Key ideas

Computational thinking means telling the computer to try a set of possible values and check which ones match the rules of the problem, then print the answer. You can change the numbers and run it again without solving the problem by hand. 1:00:19
Nested loops can try every combination of ticket counts, but this gets very slow with big numbers. A better approach mixes algebra with one loop, so the computer only has to try one value and use equations for the rest. 1:02:50
Adding 0.1 to itself ten times in code gives 0.9999999, not 1. Each operation on a float adds a very small error, and these errors build up, so you should not use the equal sign to compare floats. 1:05:46
Computers work in binary, which uses only 0 and 1, because computer hardware can easily tell two states apart, such as high or low voltage. Humans use base 10, which uses digits 0 through 9. 1:07:09
To turn a whole number into binary, you find the remainder when dividing by 2, record it, and then keep dividing the result by 2. This works well for whole numbers, and the same kind of loop can do it in code. 1:10:40

Words to know

float: A number with a decimal point, like 0.1 or 3.5, which stands for a real number.
binary: A way of writing numbers using only 0 and 1. Each place stands for a power of 2 instead of a power of 10.
floating point error: A tiny mistake that happens when a computer stores or calculates with decimal numbers, which can grow into a big surprise after many steps.
remainder: The amount left over after dividing one whole number by another. Dividing by 2 leaves a remainder of 0 for even numbers and 1 for odd numbers.

Example

Think of a light switch. It is either on or off, and that is easy for a machine to tell apart. Binary works the same way: each digit is either off (0) or on (1), so a row of switches can stand for any whole number.

3 checked practice questions for this part are in the app.

← Lecture 3: Iteration · Lecture 6: Bisection Search →

Notes written by AI (Claude) from the lecture's official transcript, so check anything important against the lecture. MIT OpenCourseWare · CC BY-NC-SA 4.0 · not affiliated with or endorsed by MIT. These notes are shared under the same license.

LessonBound · Free lecture notes · Privacy · Terms · New York