Greedy Algorithms and the Knapsack Problem: Core Notes from MIT 6.0002 Lecture 1

MIT 6.0002 Lecture 1: Optimization Models, the Knapsack Problem, and Greedy Algorithms

MIT OpenCourseWare 6.0002, Introduction to Computational Thinking and Data Science, is the sequel to the classic 6.0001, taught by Professor John Guttag. While the first half of the semester focuses on programming skills, 6.0002 shifts toward computational models and algorithmic thinking — a course about using programming to solve problems and explore the world of data science. This article distills the core themes from Lecture 1: the Knapsack Problem and Greedy Algorithms within the context of optimization models.

From Programming Skills to Computational Thinking

Professor Guttag opens the course by drawing a clear distinction between 6.0001 and 6.0002. The first course teaches you to become a programmer; the second contains "more conceptual, algorithmic content." The pace is faster, the material more abstract, and programming assignments are actually relatively straightforward — because "more effort will go into the problems being solved rather than the programming itself."

The professor underscores the only real way to learn programming with an old joke about a New York cab driver: "Someone asks how to get to Carnegie Hall. The driver says: Practice, practice, practice." The point is clear — mastering algorithms requires repeated, deliberate effort.

The central theme of the course is Computational Models — how we use computation to understand the world around us. The professor defines a model as an "experimental device" that can both explain phenomena that have already occurred (such as the history of climate change) and predict things that haven't happened yet.

The rise of computational models as scientific tools stems from the explosive growth in computing power during the second half of the 20th century. Traditional science relied on "wet labs" for physical and chemical experiments, but many systems are too complex, expensive, or time-consuming to explore entirely through experimentation. Climate science is the most telling example: we can't reproduce a century of atmospheric evolution in a lab, but we can simulate it through numerical models. Science is "moving from wet labs to computers" — traditional experiments remain important, but increasingly need computational methods to complement them. The three major categories of computational models — optimization models, statistical models, and simulation models — span everything from engineering design to machine learning, forming the methodological foundation of modern data science.

Optimization Models and the Knapsack Problem

The structure of an optimization model is straightforward: an objective function to maximize or minimize, plus a set of constraints that must be satisfied. Take a trip from New York to Boston as an example: the objective function might be "minimize travel time," while constraints could be "budget under $100" or "must arrive by 5 PM." These constraints eliminate certain feasible solutions.

Professor Guttag notes that optimization algorithms have already permeated daily life — the Waze navigation app you use during your commute is essentially solving an optimization problem to minimize travel time.

Two Variants of the Knapsack Problem

The Knapsack Problem is a classic example of an optimization problem. A burglar breaks into a house but has a bag with limited capacity. Under the constraint of "what fits in the bag," they must maximize the value of what they steal. There are two common variants:

• 0/1 Knapsack Problem: Items must be taken whole or not at all (like a solid gold bar).
• Continuous (Fractional) Knapsack Problem: You can take a fraction of an item (like grinding the gold bar into powder).

The fractional knapsack problem is relatively simple and can be solved optimally with a greedy algorithm: sort items by value density (value per unit weight) and fill the bag from highest to lowest until full. This works because the fractional version satisfies both the "greedy choice property" and "optimal substructure." The 0/1 knapsack problem, however, is far more complex — each choice affects the space of future decisions, and selecting the locally best item may prevent a globally better combination from forming. This fundamental difference leads the two variants down very different algorithmic paths.

Why Brute Force Doesn't Work

The most intuitive approach is brute force enumeration: generate all possible subsets of items (the power set), eliminate those that exceed the weight limit, and pick the highest-value one that remains. This is logically sound but completely impractical.

The Problem with Exponential Complexity

The crux of the issue is computational scale. For n items, the power set has 2^n subsets. When n=100, the number of combinations is astronomically large for any computer; in real-world optimization problems, n is often close to 1,000 or even millions. Brute force fails completely.

The more discouraging conclusion is that this isn't a failure of algorithm design. The knapsack problem — and many other optimization problems — are inherently exponentially hard (NP-hard). NP-hard (Non-deterministic Polynomial-time hard) is a central concept in computational complexity theory, introduced by Stephen Cook in 1971. It describes a class of problems "at least as hard as the hardest problems in NP." The 0/1 knapsack problem is proven NP-hard, meaning that unless P=NP (a Millennium Prize Problem that remains unsolved), no algorithm can solve it exactly in worst-case polynomial time. This theoretical conclusion has profoundly shaped algorithm design philosophy: engineers must learn to trade off exactness against efficiency, turning instead to heuristics, approximation algorithms, or dynamic programming. Since no perfect solution exists, the course shifts toward finding solutions that are "good enough."

Greedy Algorithms: Efficient but Flawed

The intuition behind a greedy algorithm is simple: as long as there's space in the bag, pick the "best" available item and add it. Repeat until nothing more fits.

The key question is how to define "best." Using a meal with a calorie budget as an analogy, "best" could mean:

• Highest value
• Lowest cost (e.g., fewest calories)
• Highest value density (value/cost ratio)

Python Implementation: A Flexible Greedy Strategy

The professor's implementation uses an elegant design — a flexible greedy algorithm that accepts a keyFunction parameter to define the sorting criterion, allowing the same greedy logic to accommodate different definitions of "best." This also introduces Python's lambda expressions: anonymous functions without a name.

Lambda expressions trace back to the λ-calculus (Lambda Calculus) proposed by mathematician Alonzo Church in the 1930s, which forms the theoretical basis of functional programming languages. In Python, a lambda is syntactic sugar that lets developers create simple anonymous function objects without defining a named function — commonly used with higher-order functions like sorted(), map(), and filter(). For example, lambda x: 1/food.getCost(x) reverses the sort order so that lower-calorie foods are prioritized. The professor offers a practical rule of thumb: use lambdas for simple one-liners; once the logic gets too complex for a single line, switch to a named def function because it's easier to debug — a reflection of an important software engineering principle: readability and maintainability come before conciseness.

In terms of algorithmic complexity, greedy algorithms are quite efficient: sorting takes O(n log n), plus a single pass at O(n), for a total complexity of O(n log n). It's worth noting that Python's built-in sorting algorithm, Tim Sort, was designed by Tim Peters in 2002. It combines the strengths of merge sort and insertion sort, exploiting the "partially sorted" patterns common in real-world data. It guarantees O(n log n) in the worst case and can approach O(n) on nearly-sorted data. It has since been adopted by Java, Android, Swift, and other platforms. Even at millions of items, this scales easily.

Local Optimum ≠ Global Optimum

Experimental results reveal the core flaw of greedy algorithms. Given a 750-calorie budget:

• Value-greedy: selects burger, pizza, and wine → total value 284.
• Cost-greedy: selects apple, wine, cola, beer, and donut → total value 318.

The same problem, with different definitions of "best," yields dramatically different results.

The Hill-Climbing Analogy: Why Greedy Fails

The professor uses "hill climbing" to explain this fundamental limitation: a greedy algorithm always picks the locally optimal choice (never backtracking), but a sequence of locally optimal choices does not necessarily add up to a global optimum. It's like a hiker who always walks uphill — they may end up on a small local hill and miss the higher mountain peak (global maximum).

Theoretically, a greedy algorithm is only guaranteed to find the global optimum when the problem satisfies both the "greedy choice property" and "optimal substructure." The 0/1 knapsack problem does not satisfy the greedy choice property, so any greedy strategy can only provide an approximate solution, not an exact one. What's worse, no single definition of "best" is guaranteed to always work — when the budget is expanded to 1,000 calories, value-greedy actually wins (424 vs. 413). In other words, you can't know in advance which greedy strategy is best, and sometimes no greedy strategy can reach the optimal solution at all.

Summary: From "Solvable" to "Solved Well"

Through the classic example of the knapsack problem, this lecture clearly illustrates the thinking framework for optimization problems: from informal description to mathematical formulation, then to algorithm design and complexity analysis. Greedy algorithms earn their place as practical tools for tackling exponentially hard problems through their simplicity and efficiency — but their "local optimum trap" reminds us that a fast answer isn't always the best answer.

The professor previews the next lecture, which will introduce dynamic programming as a way to guarantee finding the optimal solution to the knapsack problem without resorting to brute force. The core idea of dynamic programming is to decompose a large problem into overlapping subproblems and cache intermediate results, avoiding exponential search in polynomial time. This is the crucial step in 6.0002's journey from "solvable" to "solved well." For learners looking to strengthen their algorithmic thinking and move into data science, this course provides an excellent starting point.

Key Takeaways