Algorithms

Source: Concepts adapted from Ace the Data Science Interview — Chapter 9 (“Coding”) by Kevin Huo & Nick Singh. Rewritten in original wording for this course.

Recursion, greedy, and dynamic programming (especially knapsack) show up constantly. Sorting gets its own deep dive in Sorting algorithms with step animations and implement-all-the-sorts labs.

Recursion vs iteration

A recursive function needs a base case and a recursive case. Naïve Fibonacci recomputes the same fib(k) exponentially often and can blow the call stack. Iterative Fibonacci (or memoized recursion) is $O(N)$ time.

Quiz

Recursion (harder)

1 / 3

Naïve recursive Fibonacci without memoization is typically…

Pick an answer to see if you are right.

Greedy algorithms

Pick the locally best option each step. Works for canonical coin systems; fails on 0/1 knapsack. Say the greedy-choice property out loud — or switch to DP.

Quiz

Greedy (harder)

1 / 3

Items (w,v)=(2,3),(3,4),(4,5) with W=5. Optimal 0/1 value is…

Pick an answer to see if you are right.

Dynamic programming & knapsack

Needs optimal substructure + overlapping subproblems. Top-down memo or bottom-up table.

For 0/1 knapsack with capacity $W$ and item weight $w_i$, value $v_i$:

$f[j] = \max(f[j], f[j-w_i]+v_i)$

Loop $j$ downward so each item is used at most once. Loop upward for unbounded/complete knapsack.

Step through the same items both ways:

Quiz

Knapsack & DP (harder)

1 / 5

Why does 0/1 knapsack iterate j from W down to wᵢ?

Pick an answer to see if you are right.

Written: knapsack tradeoffs

0/2 solved

0/1 vs unbounded

Using “downward” and “reuse”, explain:

Explain how the 1-D DP loop direction encodes 0/1 vs unbounded knapsack, and give a tiny numeric counterexample where ratio-greedy fails for 0/1.

Minimum 45 words. Your answer must include: “downward”, “reuse”.

0 words/ 45 min

Meet the writing requirements, then you can open the model answer.

Labs: knapsack variants

Other classic practice

Next: Sorting algorithms (implement ≥5 sorts + grid animations) · Prev: Data structures.