Lecture notes · Thinking with Data · Lecture 1

Introduction and Optimization Problems

MIT 6.0002 Intro to Computational Thinking and Data Science, 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 introduces computational models and explains optimization problems, using a travel example and the knapsack problem.

Key ideas

A computer model is a tool that helps us explain what has already happened or predict what has not happened yet. Science is moving from the wet lab into the computer. 4:12
An optimization model has an objective function, which is a goal to either maximize or minimize. For a trip, the goal might be to minimize travel time. 5:39
Constraints are rules you must obey, such as a budget. They remove some possible answers from consideration. 6:23
The knapsack problem asks you to choose the most valuable items that fit in a bag with limited space. You must balance value against the size limit. 8:34
In the 0/1 version of the knapsack problem, you either take a whole item or leave it. You cannot take part of it. 9:46

Words to know

objective function: The goal you are trying to reach, such as making something as large or as small as possible.
constraints: Rules or limits you have to follow, which rule out some choices.
knapsack problem: A puzzle where you pick items to carry in a bag that can only hold so much, aiming for the most value.
0/1 knapsack problem: The knapsack puzzle where each item must be taken whole or left behind completely.

Example

Imagine you want to get from New York to Boston as fast as possible, but you only have $100. The goal of fastest travel is the objective function, and the $100 limit is a constraint. The $100 limit rules out the plane, so you are left with other choices.

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

Part 2 · 10:00–20:00

This part explains why a simple greedy method works for the easy version of the knapsack problem, why it can fail for the all-or-nothing version, and why trying every option is too slow for large problems.

Key ideas

In the continuous (fractional) knapsack problem, you can take parts of items. The lesson says it is easy: fill the bag with the most valuable thing first, then the next, until the bag is full. 10:16
A greedy algorithm means you always take the best available choice right now and move on. It is simple, but it does not always give the best overall answer. 11:01
In the 0/1 knapsack problem, you must take a whole item or leave it. Each choice changes what fits later, so the greedy method is not guaranteed to be best. 12:27
The problem can be written in math. Each item has a value and a weight, and a vector of 0s and 1s shows which items you took. The goal is to maximize total value without going over the weight limit. 15:05
Brute force tries every possible set of items and picks the best one that fits. It always finds the right answer, but for large numbers of items it takes far too long. 18:01

Words to know

greedy algorithm: A method that always picks the best option available at each step, without looking ahead.
brute force: Trying every possible answer one by one and keeping the best one that works.
power set: The full list of every possible group you can make from a set of items, including the empty group and the group with everything.
exponential: Growing very fast, so each extra item roughly doubles the work needed. Exponential problems get out of hand quickly.

Example

Imagine packing a suitcase with a limit. If you can cut a bag of sugar into any amount, you can fill the suitcase neatly with the best stuff first. But if every item is a whole box, picking the biggest box first might stop you from fitting two smaller boxes that together are worth more.

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

Part 3 · 20:00–30:00

This part shows how a simple greedy method picks a meal within a calorie budget, and how fast that method runs.

Key ideas

Before you can pick the best items, you have to decide what 'best' means. It could be the most value, the fewest calories, or the highest value per calorie. 20:03
The meal problem is a knapsack problem: you have a limited budget (750 calories here) and must choose the best mix of items that fits inside it. 20:44
The greedy algorithm uses a key function to sort items from best to worst, so the same method works no matter how 'best' is defined. 22:59
The algorithm goes down the sorted list and adds each item that still fits. It cannot stop at the first item that is too big, because a smaller item further down might still fit. 24:56
The algorithm takes about n log n steps, mostly because of the sort. The loop itself only takes n steps, so the sort dominates. That makes the method very efficient even for large lists. 28:03

Words to know

greedy algorithm: A method that makes the best-looking choice at each step and never goes back to change it.
knapsack problem: A puzzle where you must pick items to fit into a limited space or budget, getting the most value without going over.
side effect: A change a function makes to something outside itself, such as altering a list that was passed in. Good code tries to avoid this.
order n log n: A way of describing how the number of steps grows as the input grows. Here it means the work grows a bit faster than the list size, but still stays manageable.

Example

Imagine packing a suitcase with a weight limit. You sort your items from most useful to least useful, then add each one that still fits. If a big item is too heavy, you skip it and check the smaller ones after it. That is the same idea as the greedy method in this lesson.

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

Part 4 · 30:00–40:48

This part shows how a greedy algorithm picks the best-looking choice at each step, why that can miss the best overall answer, and how the lambda shortcut builds a small function inline.

Key ideas

The menu items are sorted so the cheaper ones get picked first. Here, cost means the total number of calories. 30:00
A lambda is a short, unnamed function written in one line. It takes some inputs and returns the result of one expression. 30:19
A greedy algorithm makes the best-looking choice at each step. Those local choices do not always add up to the best overall answer. 37:03
The hill-climbing example shows how a greedy walk can stop on a small peak instead of the highest one. 38:34
No single way of defining 'best' always works. A greedy algorithm cannot always find the optimal solution, and a better method is coming on Wednesday. 40:31

Words to know

lambda: A short way to write a small function in one line, without giving it a name.
anonymous function: A function that has no name. You define it where you use it, like a quick one-off tool.
greedy algorithm: A method that always takes the option that looks best right now, without planning ahead.
local maximum: A high point that is higher than everything right next to it, but not the highest point overall.

Example

Imagine climbing a hilly area in fog and always stepping uphill whenever you can. You might reach the top of a small hill and stop, even though a much taller mountain is nearby. The lesson uses this to show why a greedy choice at each step can miss the best overall result.

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

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