Chapter map

Where this sits in CS 300. Chapter 1 taught you how to type a loop; chapter 2 teaches you how to decide which loop to write when you haven’t been given one. This is the bridge between “I can code” and “I can solve a novel problem.” Every later chapter is a specific data structure; this chapter is the meta-skill of picking an algorithmic strategy in the first place.

What you add to your toolkit here:

A vocabulary for problems vs. algorithms, and for what makes one algorithm “better” than another (correctness, speed, memory, simplicity).
A recursive mindset: base case + smaller subproblem. Factorial and binary search are the training wheels; BSTs, merge sort, and graph traversal all run on this.
Three named strategies you’ll reach for repeatedly: heuristic, greedy, dynamic programming. Knowing when each is appropriate is half the exam.
An ethics / data-privacy framework so that the code you write doesn’t just work but is defensible when someone asks why you chose to collect or expose certain data.

Mastery checklist — you should be able to, without references:

State the two ingredients every recursive function needs, and show what goes wrong if either is missing (infinite recursion / wrong answer).
Write factorial(n) and binarySearch(v, t) recursively in C++ and iteratively, and argue when each form is appropriate.
Explain why naïve recursive Fibonacci is exponential while the iterative / memoized version is linear — in terms of the recursion tree, not hand-waving.
Given a new problem, correctly classify it as a candidate for greedy, DP, or neither, and defend the choice with one of the structural tests (greedy-choice property, optimal substructure, overlapping subproblems).
Walk through the fractional-knapsack greedy proof (“always pick highest value/weight ratio next”) and know why the 0/1 variant is not solvable greedily.
Identify overlapping subproblems in an LCS-like problem and write the 2D recurrence relation before touching code.
Name at least one privacy or ethics consideration that could change your design decision on a data-driven feature.

Looking ahead. Chapter 3 gives you the formal language (Big-O) to justify the “faster” and “slower” claims you made informally here. The sorting algorithms in ch. 3 are concrete instances of the strategies here: insertion/selection sort are incremental, merge/quicksort are divide-and-conquer, radix sort is a non-comparison heuristic. Expect ch. 3 to be easier if your ch. 2 recursion intuitions are solid.

2.1 Introduction to Algorithms

Chapter 1 covered the mechanics of C++ — vectors, strings, loops. Chapter 2 starts asking a different question: given a problem, what sequence of steps actually solves it, and how do you compare one sequence against another? That is the subject of algorithms, and it is the real content of this course.

Problems vs. algorithms

Two words that get used interchangeably but mean different things.

A problem and one algorithm that solves it

Problem: Given an array of numbers, what is the maximum value?

Algorithm (pseudocode):

FindMax(a):
    max = a[0]
    for i = 1 to a.size - 1:
        if a[i] > max:
            max = a[i]
    return max

The problem specification does not mention a loop, or max, or i. Those are implementation decisions the algorithm makes. A different algorithm — e.g., sort the array and return the last element — solves the same problem with different steps and different efficiency.

Why this matters: picking the right algorithm is the job

Most interesting problems you will ever see have already been reduced to a small set of well-known subproblems, each with a well-studied algorithm. Half of being a good engineer is recognizing which known problem the thing in front of you actually is.

::: center Domain Problem Common algorithm

DNA analysis Longest shared subsequence Longest common substring E-commerce / search “Is this product in stock?” Binary search Navigation Fastest route A $\to$ B Dijkstra’s shortest path Scheduling Which tasks can run first? Topological sort Compilers / build What to rebuild after a change DFS on a dependency graph Spell check / autocomplete Closest word to a typo Edit distance (DP) :::

The CS 300 syllabus is essentially a tour of the right-hand column — sorting, searching, hashing, trees, heaps, graph traversal. Once you can name the tool, the implementation becomes mechanical.

What makes an algorithm “good”?

The dominant metric is runtime growth — how the number of steps changes as the input gets bigger. This is the subject of Chapter 2 proper.

NP-complete problems: when no fast algorithm is known

Some problems have resisted every attempt to find an efficient algorithm. These are the NP-complete problems.

2.2 Problem Solving

Knowing C++ is a prerequisite for writing code, but it is not what makes programs work. The hard part — the part people are actually paid for — is problem solving: figuring out a methodical sequence of steps that turns the input into the desired output. The programming language is just the notation you write that sequence down in, the way English is the notation a chef writes a recipe down in. Good recipes come from good cooking, not good English.

A non-programming example: matching socks

Three kinds of socks sit unsorted in a drawer. You want one matching pair.

A programming-flavored example: sorting name tags

1000 name tags, currently sorted by first name, need to be re-sorted by last name.

The 64-person greeting problem

An organizer wants every person at a 64-person meeting to greet every other person for 30 seconds. How long does this take?

A usable workflow

The approach this course will try to instill, roughly in order:

Read the problem until you can restate it in one sentence without looking at the prompt. If you cannot, you haven’t understood it yet; coding will not help.
Solve a tiny example by hand. Before writing code, walk through the problem with a three- or four-element input. This usually exposes missing details and suggests an algorithm.
Describe an approach in pseudocode or English. Steps, not syntax. If the approach doesn’t work on paper, C++ will not save it.
Estimate the cost. Will this scale to the largest input the problem allows? If no, find a better approach before you write any code.
Translate to C++. Now the language matters. Idiomatic vectors, bounds checking, .at() while debugging, algorithms from <algorithm> where they fit.
Test with the tiny example from step 2. If the output does not match, trace the loop ( methodology).

Two paths to an algorithm: reduce, or design

The workflow above leaves the question of which algorithm implicit. MIT 6.006 frames it as a top-level binary choice:

Reduce to a problem you already know. If the problem looks like search, reach for a search data structure (array, hash table, BST). If sort, reach for a sort algorithm (insertion, merge, radix). If shortest path, a graph algorithm (BFS, Dijkstra, Bellman-Ford). The cs-300 syllabus is essentially this catalog of named problems and their canonical solutions.
Design your own (recursive) algorithm. If no known problem fits, you’re inventing. The strategies in — (recursion, divide-and-conquer, DP, greedy, heuristics) are the design patterns for that case.

The reduce path is faster when it applies, which is most of the time on a coursework or job-interview problem. Train the recognition reflex first; the design strategies are what you fall back on when recognition fails.

2.3 Computational Problem Solving

framed problem solving in general terms. This section narrows in on the specific style of thinking that computing demands, which cognitive-science and CS-education literature has settled on calling computational thinking. It is four habits — decomposition, pattern recognition, algorithms, and abstraction — applied together. The names are generic; the habits are not.

The input > process > output model

Every program, no matter how large, fits the same shape at the top level: take input, compute, produce output (and/or persistent side effects). Keeping this shape in mind while designing prevents the common trap of conflating “how data gets in” with “what we do with it.”

Primality check, top-level view

INPUT:    a positive integer n
PROCESS:  decide whether n has any divisors other than 1 and n
OUTPUT:   "prime" or "not prime"

The process step is where the algorithm lives. The input and output steps are routine — read an int, print a string — and should not dominate your design time.

The four habits of computational thinking

Worked example: is $n$ prime?

Watch the four habits in action on one problem.

Decomposition.

Big question (“is $n$ prime?”) into smaller yes/no questions: is it divisible by 2? by 3? by 4? … If any answer is yes, $n$ is not prime; if all are no, it is prime.

Pattern recognition.

Two useful observations:

We can stop the first time we see a divisor — we don’t need to check the rest.
No factor of $n$ (other than $n$ itself) can exceed $n/2$ , so we never need to test past there. In fact, no factor exceeds $\sqrt{n}$ , which is a much tighter bound.

Algorithm.

IsPrime(n):
    if n < 2: return false
    for d = 2 to sqrt(n):
        if n mod d == 0: return false
    return true

Abstraction.

The algorithm doesn’t depend on any specific value of $n$ ; it works for every positive integer. Expressed as a function it becomes a reusable tool.

C++ translation

#include <cmath>

bool is_prime(int n) {
    if (n < 2) return false;
    int limit = static_cast<int>(std::sqrt(n));
    for (int d = 2; d <= limit; ++d) {
        if (n % d == 0) return false;
    }
    return true;
}

Three pattern-recognition wins compound here: stop at sqrt(n) instead of $n/2$ , return as soon as a divisor is found, and handle the $n < 2$ edge case up front so the loop body doesn’t have to.

Second example: sum of 1 to 100

Decomposition.

Add numbers one at a time: $1 + 2$ , then $+ 3$ , …

Pattern recognition.

Pair the numbers from the ends in: $(1 + 100), (2 + 99), (3 + 98), \ldots$ Each pair sums to 101, and there are 50 pairs. Total: $50 \cdot 101 = 5050$ .

Algorithm.

The closed-form $\dfrac{n(n+1)}{2}$ computes the sum in $O(1)$ rather than $O(n)$ .

Abstraction.

The formula works for any positive $n$ , not just 100. It generalizes further to arithmetic sequences.

Two implementations, same output

// O(n) loop -- decomposition only
int sum_loop(int n) {
    int s = 0;
    for (int i = 1; i <= n; ++i) s += i;
    return s;
}

// O(1) closed form -- pattern recognition plus algebra
int sum_formula(int n) {
    return n * (n + 1) / 2;
}

For $n = 100$ both return 5050. For $n = 1{,}000{,}000{,}000$ , only the second one finishes in microseconds.

The loop from revisited

The workflow from the previous section is computational thinking in practice:

::: center Workflow step CT concept

Restate the problem (prerequisite) Solve a tiny example by hand decomposition Spot the structure pattern recognition Write pseudocode algorithm Generalize to a function abstraction Estimate the cost pattern recognition (again) Translate to C++ implementation Test on the tiny example verification :::

2.4 Recursive Definitions

A recursive algorithm solves a problem by reducing it to a smaller instance of the same problem and combining the answer. It is the same mental move as mathematical induction, and it unlocks a surprising number of problems that are awkward to express with loops alone — tree traversals, divide-and-conquer sorts, graph searches, backtracking puzzles. The entire back half of this course leans on it.

The anatomy of every recursive function

The template

ReturnType solve(Input x) {
    if (is_base_case(x)) {
        return direct_answer(x);        // base case
    }
    Input smaller = reduce(x);          // make progress
    ReturnType sub = solve(smaller);    // recurse
    return combine(x, sub);             // combine and return
}

Every recursive function you will write is some fill-in-the-blank version of this skeleton.

SRTBOT: a fuller version of the template

The 3-part template above (base, reduce, combine) is the core of recursive algorithm design. MIT 6.006 expands it into a 6-step recipe — mnemonic SRTBOT — that adds the explicit checks the abbreviated template leaves implicit:

Subproblem definition. State the meaning of a subproblem in words, in terms of parameters. Often subsets of input: prefixes, suffixes, contiguous substrings.
Relate. Express the subproblem solution in terms of smaller subproblems. The design pattern: identify a question whose answer would reduce to smaller subproblems, then locally brute-force all possible answers.
Topological order. Argue the relation is acyclic — subproblems form a DAG — so the recursion terminates.
Base cases. Solutions for the smallest subproblems where the relation breaks down.
Original problem. Show how to compute the answer to the original problem from subproblem solutions. Use parent pointers to recover the actual solution, not just the objective value.
Time analysis. Sum work over subproblems ( $\sum_{x \in X} \text{work}(x)$ , treating recursive calls as $O(1)$ ).

The 3-part template is the SRTBOT core: base = step 4, reduce + combine = step 2. SRTBOT pays off when you start writing dynamic-programming algorithms in , where the topological-order argument and the work-per-subproblem analysis become the actual content of the design.

Example 1: factorial

$n! = n \cdot (n-1) \cdot (n-2) \cdots 2 \cdot 1$ , with $1! = 1$ as the base.

Factorial in C++

long long factorial(int n) {
    if (n <= 1) return 1;             // base case
    return n * factorial(n - 1);      // recursive case
}

Trace for $n = 4$ :

factorial(4) = 4 * factorial(3)
             = 4 * 3 * factorial(2)
             = 4 * 3 * 2 * factorial(1)
             = 4 * 3 * 2 * 1
             = 24

Example 2: cumulative sum

Sum of $0 + 1 + 2 + \cdots + n$ . Base case: sum to $0$ is $0$ .

sum(n)

int cumulative_sum(int n) {
    if (n == 0) return 0;
    return n + cumulative_sum(n - 1);
}

$\texttt{sum}(4) = 4 + 3 + 2 + 1 + 0 = 10$ .

This is a great “first recursion” exercise, but the closed form $n(n+1)/2$ is O(1) and doesn’t risk stack overflow. Recursion here is pedagogy, not the right tool.

Example 3: reverse a vector by swapping from both ends

A recursive rewrite of the reversal loop from .

Reverse in place, recursively

void reverse_list(std::vector<int>& v, int lo, int hi) {
    if (lo >= hi) return;              // base: 0 or 1 element left
    std::swap(v[lo], v[hi]);           // work at this layer
    reverse_list(v, lo + 1, hi - 1);   // recurse on the inside
}

// Caller:
reverse_list(v, 0, v.size() - 1);

Compare to the loop in . The recursion mirrors the structural invariant directly: the outer layer is done; reverse the inner layer. Some programmers find that clearer than the v.size() / 2 loop bound.

What can go wrong

1. Missing or unreachable base case

int factorial(int n) {
    return n * factorial(n - 1);   // never stops
}

factorial(0) calls factorial(-1) calls factorial(-2) … the program crashes with a stack overflow. Every recursive function needs a base case that’s reachable from every legal input.

2. Recursing on the same or larger subproblem

int f(int n) {
    if (n == 0) return 0;
    return f(n) + 1;              // same n -- infinite recursion
}

If the recursive call isn’t on a strictly smaller input (or strictly closer to the base case), recursion doesn’t terminate. A useful habit: write down a measure — an integer that decreases on every call — and confirm it reaches the base.

Recursive strategies, classified by call-graph shape

A recursive call graph (vertex per call, directed edge $A \to B$ if $B$ calls $A$ ) must be acyclic for the recursion to terminate. The shape of that DAG corresponds 1:1 with named algorithm-design strategies you’ll meet in —:

::: center Strategy Call-graph shape

Brute force Star (all calls at one level) Decrease & conquer Chain (each call has one child) Divide & conquer Tree (calls split, no overlap) Dynamic programming DAG (calls overlap; reuse via memo) Greedy / incremental Subgraph (only one path explored) :::

This is the unifying framing for the rest of the chapter. binary search is decrease-and-conquer (chain); naive Fibonacci is divide-and-conquer with overlap (a tree that wants to be a DAG); DP is the corresponding DAG fix; greedy commits to one branch instead of exploring the whole shape. When you can sketch the call graph for a small input, you can usually name the strategy by inspection.

When to reach for recursion

Recursion and induction — the same idea

A correctness argument for recursion mirrors a proof by induction:

Base case. The base-case answer is correct by direct inspection.
Inductive step. Assume the recursive call returns the correct answer for the smaller input. Show that the combine step produces the correct answer for the current input.

2.5 Recursive Algorithms

introduced the mechanics of recursion on small arithmetic examples. This section applies the same three-part template (base, reduce, combine) to two algorithms you will actually use: Fibonacci (a warning sign about naive recursion) and binary search (a textbook win for recursion). Read them side by side — same shape, wildly different efficiency.

Fibonacci: the cautionary tale

The definition is a recurrence, so the recursive implementation writes itself:

Naive recursive Fibonacci

long long fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

Base cases: $n = 0$ and $n = 1$ . Recursive case: sum of two smaller subproblems.

This function is catastrophically slow

fib(50) takes minutes. fib(60) won’t finish today. The reason: fib(n) calls both fib(n-1) and fib(n-2), which each call two more, and so on. The number of calls grows roughly like $\phi^n \approx 1.618^n$ . The recursion tree has billions of nodes, almost all of them computing values you’ve already computed:

                fib(5)
               /      \
          fib(4)       fib(3)
         /     \      /     \
      fib(3)  fib(2) fib(2) fib(1)
      ...

fib(3) is computed twice, fib(2) three times, fib(1) five times. This is the canonical example of a correct recursive algorithm that is unacceptably slow.

Two standard fixes

Memoization: remember each result the first time you compute it. Recursion plus a cache turns $O(\phi^n)$ into $O(n)$ .

Iteration (bottom-up): just build the sequence from the bottom in a loop — no recursion, $O(n)$ time, $O(1)$ space.

long long fib_iter(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; ++i) {
        long long next = a + b;
        a = b;
        b = next;
    }
    return a;
}

The shape of the recurrence makes naive recursion tempting. Recognizing overlapping subproblems — a job for pattern recognition () — tells you to cache or iterate instead.

Binary search: the textbook win

Here recursion earns its keep. Binary search on a sorted array finds a key in $O(\log n)$ comparisons — dramatically faster than the linear $O(n)$ scan from .

Recursive binary search

int binary_search(const std::vector<int>& a, int lo, int hi, int key) {
    if (lo > hi) return -1;                          // base: empty range
    int mid = lo + (hi - lo) / 2;                    // avoid overflow
    if (a[mid] == key)  return mid;
    if (a[mid] < key)   return binary_search(a, mid + 1, hi, key);
    else                return binary_search(a, lo, mid - 1, key);
}

// Caller:
int idx = binary_search(v, 0, v.size() - 1, 42);

Tracing binary search on a concrete input

Search for 42 in {\normalfont (14, 26, 42, 59, 71, 88, 92)}

bs(v, 0, 6, 42):   mid = 3,  v[3] = 59.  59 > 42  ->  search left
bs(v, 0, 2, 42):   mid = 1,  v[1] = 26.  26 < 42  ->  search right
bs(v, 2, 2, 42):   mid = 2,  v[2] = 42.  found. return 2

Three comparisons to find the key in a 7-element list. A linear scan would also take 3 here, but scale the list to $10^9$ elements: linear is $\sim 10^9$ comparisons, binary is $\sim 30$ . That’s the exponential-vs-logarithmic gap.

Preconditions and edge cases

std::binary_search and std::lower_bound

The standard library already ships binary search, and the iterative version it uses is somewhat faster in practice:

#include <algorithm>
bool found = std::binary_search(v.begin(), v.end(), key);

auto it = std::lower_bound(v.begin(), v.end(), key);
// it points to the first element >= key

Use these in production code; write the recursion by hand to understand it.

Side-by-side: when recursion helps and when it hurts

::: center Fibonacci (naive) Binary search

Recursive calls per step 2 1 Subproblem overlap massive none Time complexity $O(\phi^n)$ $O(\log n)$ Typical depth $n$ $\log n$ Stack risk at $n = 10^6$ overflow long before safe (depth $\sim 20$ ) :::

2.6 Data Privacy

This section interrupts the algorithms thread to cover professional ethics — specifically, how a working developer should think about confidential data. The material is short on C++ but the habits it teaches show up in every real job: which data you collect, where you store it, who can see it, and how to reason about the tradeoffs when those choices conflict.

”Alertness” as a professional habit

The textbook framing borrows a line from safety engineering: the worst failures are the ones a little alertness would have prevented. For a developer, “alertness” translates to a handful of reflexes:

Before writing code that collects a piece of data, ask whether it’s actually needed.
Before sending a file, email, or dataset, ask who else sees it along the way.
Before stepping away from a laptop with sensitive data open, lock the screen.
Before committing, check for credentials, keys, or customer data in the diff.

None of these are technical. All of them are prevented by a quick pause, and none of them take a second when they become habit.

The Company XYZ scenario (and how it should have gone)

The textbook scenario: a data analyst is hired to do a confidential job-satisfaction survey. Data collected: name, home address, supervisor, free-form criticism. Data stored: an unencrypted Excel spreadsheet on a laptop left unlocked in a break room. Data leaked: the spreadsheet, forwarded by an admin who saw it open. Fallout: harassment, lawsuit, resignations.

The two levers: collection and release

The tradeoffs are real

There is no zero-risk data practice. Every privacy protection costs something — inconvenience, reduced analytic power, slower development velocity — and the job is to consciously balance cost against risk.

::: center Precaution Tradeoff

Drop identifying fields Lose some analyses (commute distance, per-supervisor complaint patterns). Encrypt the file Extra step every time you open it; password must be remembered and rotated. Collect fewer responses Smaller sample, less statistical power. Refuse to share a dataset Slows collaboration; may block a legitimate use. Retain data longer More value for longitudinal analysis, more exposure if breached. :::

A short history of things that went wrong

The scale of real breaches is hard to picture:

::: center

2013, Target 70M+ customer records including credit-card data; stemmed from a compromised HVAC vendor login. 2013, Snowden / NSA Thousands of classified documents leaked by an insider with legitimate access. 2014, eBay 148M accounts; passwords encrypted but email and address in the clear. 2014, Sony Pictures Terabytes including emails, salaries, and HR data; a senior executive lost their job over quoted emails. 2015, Anthem 80M records including SSNs and health info. 2015, Ashley Madison 30M user identities of a service whose entire value was discretion; several suicides attributed in part to the exposure. 2017, Equifax 147M Americans’ SSNs and credit data; root cause a known Apache Struts vulnerability left unpatched. 2021, Facebook 533M user records including phone numbers scraped via a contact-import misuse.

:::

What this means for you on CS 300 and beyond

Course projects rarely handle real PII, but the habits are worth forming now:

Don’t commit credentials, API keys, or .env files to git. Add them to .gitignore before you run your first git add.
Use environment variables or a secrets manager for API tokens — never string literals in source.
When a program reads user data, think about where it lives after the program exits: in memory? in a temp file? in a log?
Treat student test data with the same care you would real data, so the habits hold when the data does matter.

2.7 Ethical Guidelines

covered the narrow question of keeping confidential data confidential. This section widens the frame: once you have data and are doing something with it, what obligations come with the work? The textbook reaches for the American Statistical Association’s Ethical Guidelines for Statistical Practice, which is a good reference point even though CS 300 is not a statistics course — every engineer who ships a system that affects people is doing applied statistics whether they call it that or not.

The one-line summary

The ASA opens its guidelines with a sentence worth memorizing:

Good statistical practice is fundamentally based on transparent assumptions, reproducible results, and valid interpretations.

Those three phrases are the compressed form of everything that follows. When a result looks impressive, ask: were the assumptions stated? can someone else reproduce it? does the interpretation actually follow from the numbers?

The five categories

The ASA guidelines organize obligations into five buckets. Roughly: what you owe your work, your data, your audience, your subjects, and your field.

1. Professional integrity and accountability.

Pick the sampling and analytic approach that actually answers the question, not the one that gives the answer you wanted.
Identify and reduce sources of bias. Disclose what you can’t eliminate.
Disclose conflicts of interest — financial, political, or otherwise. Readers get to discount your work accordingly.

2. Integrity of data and methods.

Document what you did. Not “document in principle” — the preprocessing, the filters, the parameters, the cutoffs.
Report results truthfully, including the uncertainty. “Our model is 94% accurate” is meaningless without a confidence interval, a baseline, and the data it was measured on.
Share data and code when you can, redacting or aggregating to preserve privacy when you can’t.

3. Responsibilities to the public and/or client.

Explain the tradeoffs of the approach you chose, including what it cannot tell them.
Make useful knowledge broadly available when it doesn’t compromise privacy or legitimate confidentiality.

4. Responsibilities to research subjects.

Stay current on best practices for protecting the people whose data you hold.
Protect privacy and confidentiality of subjects even when doing so costs you analytic power.

5. Allegations of misconduct.

Don’t condone — or cover for — bad practice by colleagues.
Distinguish honest error and genuine disagreement from misconduct. They look similar and are judged very differently.
Don’t retaliate against whistleblowers.

Connecting the categories to CS 300 work

“Statistical practice” sounds distant from a sophomore algorithms class. It shouldn’t. A few concrete mappings:

::: center Guideline What it looks like in CS 300 / future work

Transparent assumptions Document your time complexity, your input size assumptions, and what “works” means (average? worst case? specific distribution?). Reproducible results Fixed random seeds in tests, deterministic hash-table iteration, version-pinned dependencies. Valid interpretation “Sort X finished 2 $\times$ faster” is a claim about the specific input, machine, and compiler flags — not a universal truth. Disclose conflicts If you generated your test data with the same code you’re benchmarking, say so. Protect subjects Don’t commit student records, user IDs, or real customer data to your course repo. Don’t retaliate, don’t condone If a teammate ships a function that rounds metric values “to look better,” call it out in review. :::

The classic ways analyses go bad

Unethical analysis often doesn’t look like fraud — it looks like a slightly wrong choice at each of five steps that compound into a misleading conclusion.

A short CS 300 reproducibility checklist

Even in course projects, form the habits now:

Seed any randomness you use in benchmarks or tests.
Record compiler, flags, CPU, and input size alongside every performance number.
Version the dataset. “The bids.csv we were given” is not enough — keep a hash or a dated copy.
Rerun the whole pipeline from scratch occasionally to make sure it still produces the reported results.
Commit the analysis code next to the numbers it produced, not separately.

2.8 Heuristics

ended on a note: some problems (the NP-complete ones) have no known efficient exact algorithm. What do you do when you still have to ship? You use a heuristic — an algorithm that deliberately trades optimality for speed or simplicity. Heuristics are everywhere in production code: route planners, ranking systems, allocators, schedulers, compilers, game AI. When the exact answer is too expensive to compute, a provably-pretty-good answer in a reasonable amount of time is the whole game.

The knapsack problem: the canonical example

A greedy heuristic for knapsack

Greedy by value

Knapsack01_greedy(items, capacity):
    Sort items in descending order of value
    remaining = capacity
    chosen = empty list
    for each item in sorted order:
        if item.weight <= remaining:
            add item to chosen
            remaining -= item.weight
    return chosen

Take the highest-value item that still fits; keep going until nothing else fits. One pass, plus the sort: $O(n \log n)$ total.

``DP solves knapsack'' is true -- but only pseudopolynomially

The line above says 0-1 knapsack can be solved in $O(n \cdot W)$ time with DP, which sounds polynomial. It’s not — not in the sense algorithm theorists mean.

Strongly polynomial time is bounded by a constant-degree polynomial in input size measured in words. Knapsack’s input is $n$ items plus the integer $W$ — so input size is $O(n)$ words. But $W$ itself is one of those words: it can be as large as $2^w$ where $w$ is the word size. So $O(n \cdot W)$ can be $O(n \cdot 2^w)$ — exponential in input bits.

This is called pseudopolynomial: bounded by a polynomial in input size and input integer values. Pseudopolynomial algorithms are polynomial only when the integers are polynomially bounded in input size ( $n^{O(1)}$ ). For knapsack with $W = 2^{60}$ , $O(n \cdot W)$ is hopeless.

So 0-1 knapsack remains NP-hard — the DP doesn’t actually break the hardness. The DP is useful when $W$ is small (a few thousand, say), but fundamentally the difficulty sits in the values of the integers, not their count. Subset Sum has the same character (same DP, $O(n \cdot T)$ , pseudopolynomial in target $T$ ). Chapter 3 returns to the strongly-polynomial-vs-pseudopolynomial-vs-exponential hierarchy when it formalizes Big-O.

Self-adjusting heuristics

A different flavor of heuristic: instead of approximating an answer, the algorithm reorganizes its data structure over time based on how it’s being used, so common operations get faster.

Worked example: move-to-front on a linear search

When to reach for a heuristic (and when not to)

::: center Reach for a heuristic when Use the exact algorithm when

The problem is NP-hard and inputs are large. The problem has a polynomial-time exact algorithm (most of this course). “Pretty good, fast” is more valuable than “optimal, slow.” Optimality is required by the spec (safety, financial, legal). You can measure how close the heuristic gets to optimal and it’s good enough. You can’t measure closeness and a bad answer has real consequences. The algorithm will run on streaming / online data where you can’t see the whole input. The input is fully available and small enough to process exactly. :::

2.9 Greedy Algorithms

introduced heuristics — the idea of accepting non-optimal answers for speed. A greedy algorithm is the most common style of heuristic: at each step, commit to the choice that looks best right now, without looking ahead. Sometimes this lands you at the globally optimal answer (change-making, fractional-knapsack, activity selection, shortest paths). Sometimes it doesn’t (0-1 knapsack from ). Knowing which problems are in the first bucket and which aren’t is the real skill.

Example 1: making change (and why US coins are special)

MakeChange with US denominations

MakeChange(amount):
    while amount >= 25: take a quarter; amount -= 25
    while amount >= 10: take a dime;    amount -= 10
    while amount >= 5:  take a nickel;  amount -= 5
    while amount >= 1:  take a penny;   amount -= 1

For 91 cents: 3 quarters (75), 1 dime (85), 1 nickel (90), 1 penny (91). Total: 6 coins. That also happens to be the fewest coins possible.

Example 2: fractional knapsack — greedy is optimal

Greedy by value-per-pound

FractionalKnapsack(items, capacity):
    Sort items descending by (value / weight)
    remaining = capacity
    for each item in sorted order:
        if item.weight <= remaining:
            take all of item
            remaining -= item.weight
        else:
            take fraction = remaining / item.weight of item
            remaining = 0
            break

This is provably optimal. Intuition: at every pound of knapsack space, you prefer the item with the highest dollars-per-pound. Allowing fractions means you can always fill the knapsack, so “best value density packed first” wins. 0-1 knapsack lacks this property because you’re forced into an all-or-nothing choice at the last item.

Example 3: activity selection — and why “earliest finish” wins

Greedy by earliest finish

ActivitySelection(A):
    Sort A ascending by finish time
    chosen = [A[0]]
    current_end = A[0].finish
    for i from 1 to n-1:
        if A[i].start >= current_end:
            chosen.append(A[i])
            current_end = A[i].finish
    return chosen

Why earliest-finish is optimal: a sketch

Activity selection is one of the few greedy algorithms with a clean, short correctness proof. The 2-step template from above made concrete:

Greedy-choice property. Some optimal solution includes the activity with the earliest finish time. Why: let $\mathcal{O}$ be any optimal schedule, and let $a^*$ be the earliest-finish activity overall (call its finish time $f^*$ ). If $a^* \in \mathcal{O}$ , done. Otherwise let $a' \in \mathcal{O}$ be the activity in $\mathcal{O}$ with the earliest finish time. Since $a^*$ has the globally earliest finish, $f^* \le f(a')$ . Swap $a'$ out and $a^*$ in: the rest of $\mathcal{O}$ all started after $f(a') \ge f^*$ , so they’re still compatible with $a^*$ . The new schedule has the same number of activities, includes $a^*$ , and is also optimal. This is an exchange argument — the standard shape of a greedy-choice proof.

Optimal substructure. After picking $a^*$ , the remaining problem is: pick the most activities from those that start at or after $f^*$ . That subproblem has the same shape as the original (still an activity-selection problem, on a smaller set). Combining the greedy choice $a^*$ with an optimal solution to the remaining subproblem gives an optimal solution to the whole.

Putting them together. Greedy-choice says picking $a^*$ loses nothing. Optimal substructure says we can recurse on the remaining problem with the same algorithm. By induction on input size, the algorithm produces an optimal schedule.

This is the entire shape of every greedy-correctness proof you will write: an exchange argument for greedy-choice, plus a same-shape argument for optimal substructure. Compare to the longer DP proofs in — greedy is simpler when it applies, and that simplicity is exactly why we look for greedy-friendly structure first.

When greedy actually works

There is a pattern behind these examples. Greedy is provably optimal on problems with one of two underlying structures:

Matroid structure. Fancy name, simple idea: if the locally optimal choice is always part of some globally optimal solution, and “independent subsets” have an exchange property. Change-making with US coins, minimum-spanning-tree (Kruskal, Prim, later in course), and various scheduling problems have it.
Greedy-choice property $+$ optimal substructure. Same two ingredients that justify dynamic programming, minus the need to enumerate every subproblem. Activity selection fits here.

Greedy vs. other strategies

::: center Strategy How it decides Cost / guarantee

Greedy Best local choice, no reconsideration Fast; optimal only on certain problems Dynamic programming Remember optimal answers to subproblems, build up $O(n \cdot \text{state size})$ ; optimal when subproblems overlap Divide and conquer Split, recurse, combine Optimal; works when subproblems are independent Backtracking Try choices, undo bad ones Exponential worst case but often prunable Branch & bound Backtracking + bound pruning Exact; can be practical for small NP-hard inputs :::

2.10 Dynamic Programming

Greedy () makes one choice at each step and never looks back. Pure recursion () recomputes the same subproblems over and over. Dynamic programming (DP) splits the difference: it solves every subproblem once, stores the answer, and assembles the final answer from those stored pieces.

When the problem has overlapping subproblems and optimal substructure, DP turns exponential-time recurrences into polynomial algorithms — usually a dramatic improvement.

Example 1: Fibonacci, fixed

showed naive recursive fib blowing up exponentially because fib(n-1) and fib(n-2) recompute overlapping work. DP fixes this two ways.

Top-down memoization.

Keep a cache, check it before recursing:

Memoized recursion

#include <vector>

std::vector<long long> memo;  // sized to n+1, filled with -1

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1) + fib(n - 2);
}

Each fib(k) gets computed once. $O(n)$ time, $O(n)$ memory on the cache plus $O(n)$ on the call stack.

Bottom-up tabulation.

Build the answers iteratively from the base cases up:

Tabulated iteration

long long fib(int n) {
    if (n <= 1) return n;
    long long prev = 0, cur = 1;
    for (int i = 2; i <= n; ++i) {
        long long next = prev + cur;
        prev = cur;
        cur = next;
    }
    return cur;
}

$O(n)$ time, $O(1)$ memory, no recursion. This is usually the preferred form when the dependency structure is simple.

Example 2: longest common substring (LCS)

``LCS'' usually means subsequence, not substring

Heads up on naming. The acronym LCS in most textbooks (CLRS Ch. 15.4, MIT 6.006 Lecture 16, every DP reference you’ll Google) stands for longest common subsequence — a non-contiguous match where characters from $s$ and $t$ must appear in the same order but can have gaps in between. So ACE is a common subsequence of ABCDE and XAYCEZ.

What this section covers is the longest common substring (contiguous) variant — a different problem with a different recurrence:

::: center Substring (this section) Subsequence (standard “LCS”)

Match must be contiguous in-order, gaps allowed $L[i][j]$ if mismatch $0$ (reset) $\max(L[i{-}1][j],\ L[i][j{-}1])$ Answer location max anywhere in table $L[m][n]$ corner :::

When you see “LCS” outside this chapter — in a textbook, interview question, or Stack Overflow answer — assume subsequence unless context says otherwise. Both variants are useful; just don’t confuse them.

A classic DP where the benefit is overwhelming. Naive recursion is exponential; DP is $O(n \cdot m)$ in the two string lengths. This algorithm underlies real-world tools: DNA sequence alignment, git’s rename detection, plagiarism detection.

The recurrence.

Let $L[i][j]$ be the length of the longest common substring that ends at s[i] and t[j].

undefined

2.1 Introduction to Algorithms

Problems vs. algorithms

Why this matters: picking the right algorithm is the job

What makes an algorithm “good”?

NP-complete problems: when no fast algorithm is known

2.2 Problem Solving

A non-programming example: matching socks

A programming-flavored example: sorting name tags

The 64-person greeting problem

A usable workflow

2.3 Computational Problem Solving

The input > process > output model

The four habits of computational thinking

Worked example: is nnn prime?

Decomposition.

Pattern recognition.

Algorithm.

Abstraction.

Second example: sum of 1 to 100

Decomposition.

Pattern recognition.

Algorithm.

Abstraction.

The loop from revisited

2.4 Recursive Definitions

The anatomy of every recursive function

Example 1: factorial

Example 2: cumulative sum

Example 3: reverse a vector by swapping from both ends

What can go wrong

When to reach for recursion

Recursion and induction — the same idea

2.5 Recursive Algorithms

Fibonacci: the cautionary tale

Binary search: the textbook win

Tracing binary search on a concrete input

Preconditions and edge cases

Side-by-side: when recursion helps and when it hurts

2.6 Data Privacy

”Alertness” as a professional habit

The Company XYZ scenario (and how it should have gone)

The two levers: collection and release

The tradeoffs are real

A short history of things that went wrong

What this means for you on CS 300 and beyond

2.7 Ethical Guidelines

The one-line summary

The five categories

1. Professional integrity and accountability.

2. Integrity of data and methods.

3. Responsibilities to the public and/or client.

4. Responsibilities to research subjects.

5. Allegations of misconduct.

Connecting the categories to CS 300 work

The classic ways analyses go bad

A short CS 300 reproducibility checklist

2.8 Heuristics

The knapsack problem: the canonical example

A greedy heuristic for knapsack

Self-adjusting heuristics

Worked example: move-to-front on a linear search

When to reach for a heuristic (and when not to)

2.9 Greedy Algorithms

Example 1: making change (and why US coins are special)

Example 2: fractional knapsack — greedy is optimal

Example 3: activity selection — and why “earliest finish” wins

When greedy actually works

Greedy vs. other strategies

2.10 Dynamic Programming

Example 1: Fibonacci, fixed

Top-down memoization.

Bottom-up tabulation.

Example 2: longest common substring (LCS)

The recurrence.

Worked example: is $n$ prime?