Lecture notes · CS50: Programming in C · Lecture 3

Algorithms

Harvard CS50 Introduction to Computer Science, lecture 3, 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: the course website.

Part 1 · 0:00–10:00

This part shows why dividing a problem in half again and again is much faster than checking things one at a time, and links that idea to a phone book, a counting game, and contact search.

Key ideas

In the phone book example, checking one page at a time is slow. Splitting the search in half, again and again, is far faster, even when the book gets much bigger. 2:29
In the standing-up game, people paired off and handed their numbers to one partner, and the partner who stayed standing carried the total. Each round, about half the group sat down, so the number of people still working was cut in half each time. 4:06
Any time a problem keeps getting cut in half, a logarithm is involved. That kind of algorithm is much faster than checking every item one by one. 8:26
Phone contact search uses this same divide and conquer idea. It jumps to roughly the middle of your contacts, then searches one half, and repeats until it finds the name. 8:46

Words to know

algorithm: A clear, step-by-step set of instructions for solving a problem.
divide and conquer: Solving a problem by splitting it into smaller parts and working on each part, so the work gets smaller at every step.
logarithm: A math idea linked to repeated halving. Each time the problem is halved, the number of steps needed grows only a little, so the work stays small even when the problem is huge.
byte: A small unit of computer memory that holds 8 bits. The lesson describes memory as a grid of these small squares.

Example

Imagine finding one name in a phone book by opening it near the middle, then checking only the half that could hold the name, then halving again. This is the same idea as the standing-up game, where half the group sat down each round. Each step removes half of what is left, so the search finishes quickly.

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

Part 2 · 10:00–20:00

This part explains the search problem: how a computer finds one value in a row of stored numbers, and how knowing the numbers are sorted can change the search.

Key ideas

An array is a collection of values stored back to back in memory. This back-to-back layout is called contiguous. 11:05
A computer cannot see its whole memory at once. It can only look at one location at a time, so it has to check each spot in turn. 12:07
A search problem asks whether a value is there. The answer is true if it is found and false if it is not. 14:15
Sorting the data first costs extra work up front. That cost can be worth it if you plan to search again and again. 18:07
When the numbers are not sorted, checking from one end works, but the number of steps depends on luck. On average, it takes about half the lockers. 19:31

Words to know

array: A list of values of the same kind, stored one after another in computer memory.
contiguous: Packed together with no gaps, like bytes sitting back to back in memory.
index: The number in brackets that picks out one exact spot inside an array, such as bracket 0 or bracket 3.
linear: Going step by step in a straight line, one item after another, from one end to the other.

Example

Imagine a row of closed mailboxes, and you need to find the one with a letter for you. You cannot see inside any of them, so you must open them one at a time. If the letter is in the first box, you are lucky; if it is in the last, you have to open them all.

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

Part 3 · 20:00–30:00

This part explains two ways to search an ordered row of doors, linear search and binary search, and how to write them as pseudocode.

Key ideas

Linear search checks each door one at a time, from left to right or right to left. It gets its name because you walk along a line. 22:08
Binary search starts in the middle and throws away half of the remaining doors each time, going left or right. This works because the numbers are sorted. 25:07
Indentation matters in pseudocode. The line that returns false must come after the loop, so you only give up once every door has been checked. 22:53
Binary search has four cases to handle: the answer is in the middle, to the left, to the right, or not there at all. Checking for an empty set of doors comes first. 26:11
Linear search takes about n steps for n doors. Binary search halves the work each time, so doubling the doors adds only about one more step. 29:04

Words to know

linear search: Searching through items one after another in a straight line, from one end to the other.
binary search: Searching a sorted list by checking the middle item and cutting the list in half again and again.
pseudocode: Plain-English steps written in a code-like style, before you write real code in a programming language.
index: The position number of an item in a list, such as 0 for the first item in an array.

Example

Think of looking up a word in a dictionary. You open it near the middle, see whether your word comes before or after that page, and then ignore the half that cannot hold it. Each look throws away about half of the book.

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

Part 4 · 30:00–40:00

This part explains how computer scientists compare how fast algorithms are, using big O, omega, and theta notation, and then starts writing a linear search in C.

Key ideas

Computer scientists describe how long an algorithm takes as being 'on the order of' some number of steps, and they ignore small details that do not matter much. 30:00
Constant factors, such as a 2 or the base of a logarithm, are thrown away. When n gets very large, they do not change the overall shape of the picture. 30:43
Big O notation gives an upper bound on the steps, usually the worst case. For example, linear search is big O of n because in the worst case it checks all n items. 32:51
Omega gives a lower bound, the best case. If the upper and lower bounds match, the algorithm is theta of that amount, as with pointing at everyone to take attendance, which is theta of n. 37:33
The next step is to put linear search into C code, using an array of numbers and a loop that checks each number in turn. 38:17

Words to know

big O notation: A way of writing the most steps an algorithm might need, as its upper limit, usually for the worst case. It shows how the work grows as the input grows.
constant factor: A fixed number that multiplies the work, such as 2 times as many steps. Computer scientists ignore these when the input gets large.
omega: A symbol for the lower limit on steps, meaning the fewest steps an algorithm might need, which is its best case.
theta: A symbol used when the upper and lower limits are the same, so the algorithm takes about the same number of steps in both the best and worst cases.

Example

Imagine checking whether a name is on a list of people in a room, one person at a time. In the worst case you check everyone, so the work grows with the size of the room. If everyone stood up at once, the time would stay the same no matter how many people were there, which is a constant-time idea.

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

Part 5 · 40:00–50:00

This part shows how to stop a search early, how main reports success or failure with a number, and why C needs strcmp instead of == to compare strings.

Key ideas

The 'else' clause was wrong because it printed 'not found' on the first item that did not match. 'Not found' should only be printed after the whole array has been checked. 40:46
The program can end early by returning a value from main. By convention, 0 means success, and any other number, such as 1, 2, or 3, means failure. 41:28
When main returns a value, the program stops right there, and no code below that line runs. This is how the search stops once it finds the number. 43:17
In C, you cannot compare two strings with the same == check used for numbers. The string.h header file provides strcmp, which compares two strings. 47:15
strcmp returns 0 when the two strings are the same. So the search checks whether strcmp returns 0, not whether it returns true. 48:24

Words to know

exit status: A number a program sends back when it ends. Zero means it finished without problems, and other numbers mean something went wrong.
header file: A file that gives your program access to extra tools, such as string functions, that are not built in by default.
strcmp: A built-in C function that compares two strings. It returns 0 when they are the same.
magic number: A plain number written directly in code, such as 6, with no name to explain what it means. The lesson calls the 6 in the loop a magic number.

Example

Think of a worker who finishes a job and hands in a slip. A slip that says 0 means all went well, and a slip that says 1 or 2 means something went wrong, and the number tells the boss which problem happened. Like main returning a number, the slip is the final report, and the worker stops working once it is handed in.

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

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

This part shows why comparing strings needs a function like strcmp, why phone numbers are stored as text, and how a struct can keep a name and number together in one place.

Key ideas

Sometimes you need more than a yes or no answer. For strings, you may also want to know whether one comes before or after another in order. 50:00
The equals sign only tells you true or false. The strcmp function also tells you the order of two strings, and it returns zero when they are equal. 50:20
strcmp compares the number codes of the letters, not true alphabetical order. The lecturer calls this ASCII-betical order. 50:41
Phone numbers are best stored as strings, not integers, because they can contain pluses and dashes and can be too long for an integer. A good rule is to store something as text if you would never do math on it. 52:54
Keeping names in one array and numbers in another, lined up by position, is a bad design. The two lists can get out of sync as they grow. A struct, made with typedef, can hold a name and a number together as one person. 55:48

Words to know

strcmp: A built-in C function that compares two strings. It returns zero if they are equal, and a different number that shows which one comes first if they are not.
ASCII-betical order: The lecturer's playful name for ordering strings by comparing the number codes of their letters. It is close to alphabetical order but not exactly the same.
struct: A way to group several variables together under one name, so one value can hold more than one piece of information, such as a name and a number.
code smell: A hint that something in your code may cause trouble later, even if it works right now. The lecturer says it is a sign to look for a better design.

Example

Think of a paper contact card. The name and phone number are written on the same card, so they always stay together. Two separate lists, one of names and one of numbers, is like keeping them on different sheets of paper: if you add a card to one sheet and forget the other, the names and numbers no longer match.

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

Part 7 · 1:00:00–1:10:00

This part shows how to group related data into one custom type called a struct, and introduces a methodical, step-by-step way to sort a list of items.

Key ideas

The dot operator lets you reach inside one person in the array to get or set a field, like people[0].name. The loop can then check each person's name one at a time. 1:00:20
A struct groups several related pieces of data together, and typedef gives that group a new name you can use like any other data type. 1:02:47
If you leave a field unset, it holds a leftover value that nobody chose. Accessing it later can cause bugs or even a crash, so you should always set every field. 1:03:34
Binary search needs data that is already sorted. Sorting takes effort, so the speaker says the steps must be methodical so they can be written as code and still work for many more items. 1:04:16
A person, like the computer, can only look at one item at a time. To find the smallest, you keep a mental note of the smallest value seen so far and ignore the rest. 1:09:42

Words to know

struct: A way to group several related pieces of data together under one name, such as a person's name and number.
typedef: A keyword that gives a new, friendlier name to a data type, so you can use that name in your code.
garbage value: A leftover, random value sitting in memory that was never set on purpose, so it cannot be trusted.
pseudocode: Plain-language steps that describe what a program should do, written before the real code is typed.

Example

Imagine a row of volunteers standing in a line, and you must put them in order from smallest number to largest. You cannot see the whole line at once, so you look at one person at a time, remember the smallest number you have seen, and move people into place one step at a time.

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

Part 8 · 1:10:00–1:20:00

This part explains selection sort, a simple way to sort a list by repeatedly picking the smallest item, and compares it with a second method that fixes neighbouring pairs.

Key ideas

Selection sort works by scanning the whole list and remembering only the smallest value seen so far. It then moves that value into the first open spot and repeats for the next spot. 1:15:14
The second approach swaps neighbours that are out of order. Each pass pushes the biggest remaining value toward the end, so the list gets better bit by bit. 1:13:29
Selection sort needs only one variable in memory, so it does not keep track of where other numbers are. That is why it has to search the list again on every pass. 1:16:20
The lesson writes selection sort as pseudocode, a plain-language recipe close to code. For each position i, find the smallest value from i to the end, then swap it into position i. 1:17:25
Selection sort feels slow because it makes many comparisons, and some of them get repeated. The lesson then asks how fast or slow different sorting methods are. 1:19:38

Words to know

array: A row of storage boxes placed side by side in computer memory, each holding one value and numbered by position.
contiguous: Next to each other with no gaps, like a row of seats in a theatre that are all touching.
pseudocode: A short, plain-English outline of the steps an algorithm takes, written so it can later be turned into real code.
selection sort: A sorting method that repeatedly finds the smallest remaining value and moves it into the next spot at the front of the list.

Example

Imagine people standing in a line and asked to order themselves by number. Each time, you look along the whole line for the lowest number, walk that person to the front, and then repeat for the next spot. You only need to remember the lowest number you have seen so far, but you have to walk the line again and again.

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

Part 9 · 1:20:00–1:30:00

This part shows how to measure how many steps selection sort and bubble sort take, and why both grow roughly with the square of the list size.

Key ideas

Selection sort makes n minus 1 comparisons on the first pass, then one fewer on each later pass. Added together, this comes to n times (n minus 1) divided by 2. 1:20:59
When the list is very large, the biggest term (n squared) matters most, so we say selection sort takes on the order of n squared steps. 1:21:42
Selection sort has no early exit, so it does about n squared steps even when the list is already sorted. That is why its best and worst cases are the same. 1:23:10
Bubble sort repeats passes that swap neighbors which are out of order. Counting its steps gives about n minus 1 times n minus 1, which also grows like n squared. 1:27:35
The lesson ends by asking how bubble sort could stop early, for example when a full pass makes no swaps. It asks this question but does not answer it in this part. 1:29:47

Words to know

big O notation: A shorthand that describes how the number of steps grows as the list gets bigger. It ignores small details and keeps only the main growth pattern.
dominant term: The part of a formula that becomes the biggest and matters most when the number is large. Smaller parts can be ignored in that case.
asymptotic: Having to do with how something behaves when the input gets very large. Big O, omega and theta are called asymptotic notations.
pseudocode: A plain-English outline of a program written in a loose, code-like style, used before writing real code.

Example

Imagine each of eight people shaking hands with everyone else in the room. That is many handshakes, and the number grows much faster than the number of people. Selection sort works in a similar way, so its work grows quickly as the list gets longer.

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

Part 10 · 1:30:00–1:40:00

This part explains how to stop bubble sort early, and introduces recursion, where a function calls itself on smaller and smaller problems.

Key ideas

If one full pass through the list makes no swaps, the list is already in order, so the algorithm can stop early. This tweak can make bubble sort faster in the best case. 1:30:20
Even in the best case, bubble sort still has to look at every element, so it takes at least n steps. That is why its best case is written as omega of n. 1:30:41
Recursion is when a function calls itself. Binary search does this, because it searches the left or right half, which is a smaller version of the same job. 1:33:35
A recursive function needs a base case, a simple case where it stops calling itself. Without one, it would keep going forever or crash. 1:35:23
Recursion also describes shapes and code, not just searching. A pyramid of height 4 is a pyramid of height 3 plus one row, and this keeps going down to a single brick. The lesson then starts an iterative pyramid program that uses nested loops. 1:37:57

Words to know

recursion: When a function calls itself to solve a smaller version of the same problem.
base case: The simple situation where a recursive function stops calling itself, such as when there are no doors left to check.
iteration: Repeating the same steps again and again with a loop, such as going through each row of a pyramid.
best case: The easiest situation an algorithm could face, which shows the fewest steps it might need.

Example

Imagine counting the people in a line by asking the person in front of you to count everyone ahead, then adding one. Each person repeats the same job on a shorter line, and the person at the front, who has no one ahead, simply says zero. That final simple answer is the base case that stops the repeating.

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

Part 11 · 1:40:00–1:50:00

This part shows how to draw a pyramid of hashes using recursion, where a function calls itself, and introduces merge sort as a faster sorting method.

Key ideas

The iterative pyramid uses two nested loops. The inner loop runs up to i plus 1, so the first row prints one hash, the next prints two, and so on. 1:40:00
The recursive version draws a pyramid of height n by first drawing a pyramid of height n minus 1, then printing one more row. The function calls itself to do the first part. 1:40:00
A base case is the check that stops the recursion. Here, if n is 0 or less, the function returns without calling itself again, so it never runs forever. 1:40:00
Merge sort sorts a list by sorting its left half, sorting its right half, and then merging the two sorted halves. A list with only one number is already sorted, so that is its base case. 1:40:00
To merge two sorted lists, you repeatedly pick the smaller of the two front numbers and add it to a new list. The lesson also says that using more memory (space) can reduce the time needed to solve a problem. 1:40:00

Words to know

recursion: A way of solving a problem where a function calls itself on a smaller version of the same problem.
base case: The simple situation where the function stops calling itself, such as when there is nothing left to draw.
merge sort: A sorting method that splits a list in half, sorts each half, and then stitches the sorted halves back together in order.
array: A list of values stored one after another in memory, such as a list of numbers.

Example

Imagine you want to count a tall stack of books. You can count the stack below the top book, then add one for the top book. The stack below is a smaller version of the same job, and when there are no books left, you stop.

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

Part 12 · 1:50:00–2:01:41

This part shows how merge sort works by splitting a list in half again and again, then merging the pieces back together, and why that makes it much faster than selection sort or bubble sort.

Key ideas

Merge sort has three steps: sort the left half, sort the right half, then merge the two sorted halves. Each half is sorted by using the same three steps on a smaller list. 1:50:00
A list with only one number counts as already sorted, so it is the base case that stops the splitting. The real work happens when sorted pieces are merged together. 1:50:00
Merging two sorted lists is done by comparing the front numbers and taking the smaller one first, left hand and right hand. This is the step that does the sorting. 1:50:00
Each round of halving takes about n steps to merge everything back, and there are about log n rounds. Multiplied together, that gives n times log n steps. 1:50:00
Merge sort is faster than selection sort and bubble sort on most data, but it can be slower than bubble sort when the data is already sorted. 1:50:00

Words to know

recursion: Solving a problem by using the same method on smaller versions of that problem until the pieces are tiny enough to solve directly.
divide and conquer: Breaking a big problem into smaller parts, solving each part, and then combining the answers.
merge: Combining two already sorted lists into one sorted list by repeatedly taking the smaller front number.
big O: A way of describing how the number of steps an algorithm needs grows as the list gets bigger. It ignores constant factors.

Example

Imagine you have a messy pile of 8 playing cards. You split the pile in half, then split each half again, until every pile has one card. Then you combine neighboring piles two at a time, always placing the smaller top card first, until one full sorted pile is left.

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

← Week 2: Arrays · Week 4: Memory →

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

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