Algorithms and Computation

MIT 6.006 Introduction to Algorithms, lecture 1, 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 what a computational problem and an algorithm are, and why the course cares about proving that solutions are correct and efficient.

Key ideas

The course is about solving computational problems, but also about explaining why your solution is correct and efficient, and communicating that to other people. 1:25
A problem is a set of possible inputs, a set of possible outputs, and a rule that says which outputs are correct for each input. Several outputs can be correct for one input. 4:07
Problems are usually defined by a check: given an input and an output, you can tell whether the output is correct. Listing every correct answer one by one would take far too long. 5:15
The course wants general solutions that work for inputs of any size, using one fixed procedure, not a solution for one small case. 8:18
An algorithm is a fixed procedure or machine that takes an input and produces an output. If it produces an output, that output should be one of the correct ones. 9:44

Words to know

binary relation: A pairing rule between two groups. Here it means each input is linked to the outputs that count as correct for it.
predicate: A yes-or-no test. For a problem, it checks whether a given output is correct for a given input.
bipartite graph: A picture with two separate groups of dots, where lines only join a dot in one group to a dot in the other. Here, one group is the inputs and the other is the outputs.
deterministic: Always giving the same result for the same input, with no randomness involved.

Example

Think of a problem like an answer key that says which answers are acceptable for each question, with more than one answer sometimes allowed. An algorithm is like a student who reads a question and writes down one answer. A good student's answer should always be one that the key accepts.

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

Part 2 · 10:00–20:00

This part explains what an algorithm is, shows a birthday-matching example, and begins a proof that the example always gives the right answer.

Key ideas

An algorithm is a step-by-step procedure that takes an input and gives back one output. It solves a problem only if it returns a correct output for every valid input. 10:19
The birthday algorithm keeps a record. It interviews students one at a time, checks each birthday against the record, returns a pair if it finds a match, and otherwise adds the student to the record. If no match is found by the end, it returns none. 11:22
A verbal description like this is enough for a person to understand the method, even though a computer would need more detail. 13:24
Checking a few examples works for four people, but not for 300. To prove correctness for any size group, we use induction, which needs a base case, a hypothesis, and an inductive step. 16:23
The hypothesis for the proof says that if the first K students contain a match, the algorithm will have already returned a pair by the time it has interviewed them. Proving this for every K shows the algorithm is correct. 19:00

Words to know

algorithm: A clear set of steps that takes an input and produces an output, like a recipe.
function: A rule that gives exactly one output for each input.
induction: A way to prove something is true for every size of a group by proving it for a starting case and then showing that each step carries it to the next size.
base case: The simplest starting case in an induction proof, which is shown to be true first.

Example

Think of a teacher checking a class roster for two students with the same birthday by asking each student in turn and writing their birthday on a list. Checking a small class by hand is easy, but a school of 300 needs a proof that the method always works. Induction gives that proof without checking every possible group.

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

Part 3 · 20:00–30:00

This part explains how to prove an algorithm gives the right answer, and how to measure how efficient it is by counting basic steps instead of timing it.

Key ideas

To prove an algorithm is correct, you use induction: assume it works for the first k students, then show it still works when you add student k plus 1. [20:10] 20:10
The proof starts with a base case, which is the easiest case, such as checking zero students. After zero students, no match can exist yet, so the starting claim holds. [21:12] 21:12
The inductive step has two cases. Either the first k students already contain a match, so the algorithm has already returned it, or the match must be the new student k plus 1, which the algorithm checks directly. [22:46] 22:46
Efficiency means how fast an algorithm runs compared with other ways of solving the same problem. Timing it on a real computer is a poor measure, because the result depends on the machine and the data. Instead, count the basic operations the algorithm needs. [27:21] 27:21
Asymptotic analysis is the tool for this. It looks at how the number of operations grows as the input gets bigger, which shows how performance changes with input size. [29:21] 29:21

Words to know

inductive hypothesis: A statement you assume is true for some number of cases, so you can prove it still holds for one more case.
base case: The simplest starting case that you can show is true without any work, so the rest of the proof has a foundation.
operation: One basic step a computer does, treated as taking a fixed amount of time, such as a single comparison or a single addition.
asymptotic analysis: A way of describing how the number of steps an algorithm needs grows as the input gets larger.

Example

Imagine checking a line of people one at a time to see if any of them has a certain birthday. If you already know the first k people do not match, you only need to check person k plus 1, and you can keep going one person at a time until the line ends. This is the same step-by-step reasoning the lesson uses to prove an algorithm correct.

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

Part 4 · 30:00–40:00

This part explains how we measure how fast an algorithm runs, using input size and common growth patterns, and introduces the simple computer model used to count steps.

Key ideas

The input size is usually called n, but it depends on the problem. An n-by-n array has input size n squared, and a graph has input size equal to its vertices plus its edges. 30:00
We judge speed by how the running time grows as the input grows. Big O gives an upper bound, omega gives a lower bound, and theta means the bound is tight, bounded from above and below. 30:40
Common growth patterns, from fastest to slowest, are constant, logarithmic, linear, n log n, quadratic, and polynomial. In this class, efficient usually means polynomial. Exponential time is much worse. 32:48
To count steps, we use a simple model of a computer called the word RAM. Memory is a string of bits, and the CPU can read, change, and write small chunks of it in a fixed amount of time. 36:53
A word is the fixed-size chunk of bits the CPU takes from memory at one time. Modern computers address memory in bytes, and a 64-bit word is common today. 39:12

Words to know

big O notation: A way to describe an upper limit on how fast an algorithm's running time grows as the input gets bigger.
polynomial time: Running time that grows like n raised to a fixed power, such as n squared or n cubed. In this class, it counts as efficient.
exponential time: Running time that grows like a fixed number raised to the power of n. It gets very large very fast, so it is considered bad.
word: The fixed number of bits the computer's processor can take from memory and work on at one time.

Example

Think of a checkout line where each extra person adds the same amount of waiting time. That steady, one-for-one growth is like linear time. If the wait instead doubled with every extra person, it would grow so fast that it would quickly become unworkable, which is like exponential time.

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

Part 5 · 40:00–45:32

This part explains why computer memory has size limits, how fast a CPU can work on small versus large amounts of data, and how the course is organized.

Key ideas

A CPU can only hold a memory address of a fixed size. With 32 bits, the largest hard disk it can reach is about 4 gigabytes, so bigger drives had to be split into 4 gigabyte pieces. With 64 bits, the limit is far larger. 40:23
A CPU works on a fixed, small amount of data at once, usually two words of memory. Reading or writing one word takes constant time, which means the same amount of time no matter how big the data is. 42:14
If you have to read through n items one by one, the time grows with n. This is called linear time. 42:59
Much of the course is about data structures, which are ways of storing a large amount of data so that operations on it are fast. 43:19
To solve a problem in this course, you can either reduce it to a problem you already know how to solve, or design your own recursive algorithm, which is one that solves a problem by calling itself on smaller pieces. 44:45

Words to know

word: A fixed-size chunk of data that the CPU reads and writes as one unit.
constant time: An operation that takes the same amount of time no matter how much data is involved.
linear time: A task whose time grows in step with the amount of data, so twice the data takes about twice as long.
data structure: A way of organizing a large collection of data so you can store it and work with it quickly.

Example

Think of checking one mailbox in a building. That takes the same short time whether the building has 10 mailboxes or 1,000, which is like constant time. Checking every mailbox to find one letter takes longer as the building gets bigger, which is like linear time.

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

Lecture 2: Data Structures and Dynamic Arrays →

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