Pre-Class Lecture 17

The questions below are due on Monday November 09, 2026; 03:05:00 PM.
 
You are not logged in.

Please Log In for full access to the web site.
Note that this link will take you to an external site (https://shimmer.mit.edu) to authenticate, and then you will be redirected back to this page.

1) Pruning a Decision Tree

Recall the movie-marathon example from the previous lesson. You and your friends had six possible movies but only enough time to watch exactly three. To find every possible group, we used a decision tree that made one choice for each movie: include it in the marathon or leave it out. This generated the full power set of 2^6 = 64 movie combinations. We then filtered those combinations and kept only the groups containing exactly three movies.

That approach is correct, but it explores many branches whose results will eventually be filtered out.

If we control the recursion directly, we can stop exploring a branch as soon as we know that none of its descendants can produce a useful answer. This is called pruning. Pruning does not discard possible valid answers; it skips a branch only after the constraints prove that the branch is complete or impossible.

For fixed-size subsets, let size mean "the number of additional items this branch still needs to choose." At each node, the next item creates two decisions:

  • exclude it: recurse on the remaining items with the same size, or
  • include it: recurse on the remaining items with size - 1, then add the item to each returned subset.

For example, suppose we need to choose three movies from ["A", "B", "C", "D", "E", "F"]. After choosing "A" and excluding "B", the remaining subproblem is:

subsets_with_size(["C", "D", "E", "F"], 2)

The node records that four movies remain and two more must be chosen. Before expanding any node, ask:

  1. Has this branch already selected as many items as it needs?
  2. Are enough items left to select as many as it still needs?
Question 1: In each call, size is the number of additional movies the branch must select. Which states can stop without making another recursive call? Check all that apply.
subsets_with_size(["E", "F"], 0): this branch needs no more movies.
subsets_with_size(["F"], 2): one remaining movie cannot fill two places.
subsets_with_size(["D", "E", "F"], 2): it still has meaningful choices to make.
subsets_with_size([], 1): it still needs a movie, but none remain.

These observations give us two stopping conditions. If size == 0, the branch has made all the selections it needs. It returns [set()] so that earlier recursive calls can add the items they chose. If size > len(items), the branch needs more items than remain, so it cannot produce a valid subset and returns [].

def subsets_with_size(items, size):
    if size == 0:
        return [set()]             # this branch is complete
    if size > len(items):
        return []                  # this branch is impossible

    first, rest = items[0], items[1:]
    without_first = subsets_with_size(rest, size)
    with_first = [
        {first} | subset
        for subset in subsets_with_size(rest, size - 1)
    ]
    return without_first + with_first

Consider subsets_with_size(["F"], 2). Without pruning, the function would explore branches that include or exclude "F", even though neither could select the two movies still needed. The second stopping condition returns [] immediately and skips that unnecessary work.

Question 2: Which statements correctly describe pruning in subsets_with_size? Check all that apply.
An include branch reduces size by one because it fills one of the remaining places.
An exclude branch reduces size by one because it removes an item from consideration.
When size == 0, the branch has completed a valid selection.
When size > len(items), no descendant can contain enough selected items.
Pruning may remove valid subsets in exchange for running faster.

Decision trees generate combinations by making an include-or-exclude choice for each item. To find subsets of a desired size, we could generate the full power set and then filter its results. However, we can work more efficiently by pruning a branch as soon as it cannot produce a valid result. For example, once a branch has accumulated the target number of items, there is no need to keep exploring choices that add more items. We can extend this idea from constraints on the number of selected items to constraints on their total weight, which leads us to the knapsack problem in the next section.

2) Decision Tree Example

Imagine that you are packing a bag for a day on campus. Your bag can hold at most 10 pounds, and you are deciding whether to pack each of these items:

  • a laptop weighing 5 pounds,
  • a textbook weighing 4 pounds,
  • lunch weighing 2 pounds, and
  • a jacket weighing 3 pounds.

A decision tree can represent every possible packing list. At each level, you consider one item and create two branches: one where you leave it out and one where you pack it. For example, after considering the laptop and textbook, one node might represent the state laptop packed, textbook left out, 5 pounds used. A node therefore needs to record the choices made so far and enough information, such as the current weight, to decide which choices remain valid.

Question 3: Which description would be most useful as a node in this decision tree?
Only the name of the next item to consider
The items considered so far, which of them were packed, and their total weight
Only the number of items that were packed
Every packing list that could ever be made
Question 4: When the tree considers the jacket, what do its two outgoing branches represent?
Pack the jacket or leave it out
Pack the laptop or pack the textbook
Increase or decrease the bag's capacity
Start over with an empty bag or stop immediately

We do not need to follow every branch to the bottom. If a node represents a bag that is already over the 10-pound limit, adding or excluding later items cannot make the items already packed weigh less. We can prune that node and all of its descendants. We can also stop exploring once every item has been considered, because that node already represents a complete packing list.

Question 5: Which situations can stop being explored immediately? Check all that apply.
The laptop, textbook, and lunch have been packed, for a total of 11 pounds.
The laptop has been packed, for a total of 5 pounds, and three items remain to be considered.
The laptop and jacket have been packed, for a total of 8 pounds, and lunch remains to be considered.
All four items have been considered, so the node represents a complete packing list.

3) Knapsack Problem

So far, our decision-tree examples have treated every selected item the same: we either generated every subset or required a subset to contain a particular number of items. The knapsack problem adds two pieces of information to each item: a weight and a value. Instead of finding every subset of a certain size, we must find the subset with the greatest total value whose total weight stays within a capacity limit. The tree still makes an include-or-exclude decision for each item, but deciding whether a branch is useful now depends on the combined weights and values of the selected items.

In the knapsack problem, we must choose a subset of available items that maximizes total value without exceeding a fixed weight capacity. In the fractional version, we may take part of an item. In the discrete 0/1 knapsack version, each item must be either included or excluded. This class looks at the discrete version, where you either take an entire item or you exclude the entire item.

Suppose a knapsack can hold 10 grams and we can choose among a 5-gram gold bar worth $250, 4 grams of saffron worth $240, and a 3-gram diamond worth $1,500. Taking the items in descending order of value per gram selects the diamond and saffron, worth $1,740, but choosing the diamond and gold instead produces the better total of $1,750. This example shows why a greedy strategy based on value, value per unit weight, or weight can miss the optimal combination. Although greedy strategies are fast and may produce a good approximation, solving 0/1 knapsack exactly requires considering how the items' weights and values interact.