DSA Instant Checkpoint - Programming for Machine Learning and Business

A Focused Self-Test Before Greedy Algorithms¶

Quick pressure test: can you choose the right tool fast?¶

This notebook is intentionally short. The previous page already reviewed the whole chapter. Here, the goal is to answer compact DSA questions with confidence before the course shifts toward greedy algorithms and later dynamic programming.

By the end of this checkpoint, you should be able to¶

identify the best-fit structure or algorithm from a short prompt,
explain why one option fits better than close alternatives,
spot which topics need review before moving into optimization strategies.

checkpoint_items = [
    {
        "prompt": "Need unique products only",
        "answer": "set",
        "reason": "Sets remove duplicates and support fast membership checks."
    },
    {
        "prompt": "Need first-in, first-out service order",
        "answer": "queue",
        "reason": "Queues preserve arrival order."
    },
    {
        "prompt": "Need minimum-hop path on equal-cost edges",
        "answer": "bfs",
        "reason": "Breadth-first search explores by layers."
    },
    {
        "prompt": "Need cheapest path on weighted edges",
        "answer": "dijkstra",
        "reason": "Weighted routes require cost-aware updates."
    },
]

print("Instant checkpoint answers")
print("=" * 28)
for index, item in enumerate(checkpoint_items, start=1):
    print(f"{index}. {item['prompt']}")
    print(f"   Best answer: {item['answer']}")
    print(f"   Why        : {item['reason']}")
    print()

Instant checkpoint answers
============================
1. Need unique products only
   Best answer: set
   Why        : Sets remove duplicates and support fast membership checks.

2. Need first-in, first-out service order
   Best answer: queue
   Why        : Queues preserve arrival order.

3. Need minimum-hop path on equal-cost edges
   Best answer: bfs
   Why        : Breadth-first search explores by layers.

4. Need cheapest path on weighted edges
   Best answer: dijkstra
   Why        : Weighted routes require cost-aware updates.

Decision Map¶

Worked example¶

Suppose a team asks three questions in one meeting:

“Which customers appear more than once in this spreadsheet?”
“Which support ticket should be served next?”
“What is the cheapest delivery route between hubs?”

Those point to three different choices: set, queue, and dijkstra. A strong DSA learner does not just remember syntax; they notice the shape of the problem quickly.

Interactive Code¶

Guided Practice¶

Which structure best supports an undo feature in a text editor?¶

stackCorrect. Undo usually removes the most recent action first.

queueA queue preserves arrival order, not reverse-most-recent behavior.

setA set is about uniqueness, not undo order.

dictionaryA dictionary maps keys to values, but it does not model undo flow.

If every road segment has the same cost, which algorithm gives the fewest-step route first?¶

DFSDFS may go deep quickly, but it does not guarantee the fewest hops first.

BFSCorrect. BFS checks the graph layer by layer.

Topological sortTopological sort is for dependency ordering in DAGs, not shortest hops.

Cycle detectionCycle detection answers whether a loop exists.

What should you verify before trusting a topological ordering?¶

That the graph has the highest possible weightWeights are not the issue here.

That the dependency graph has no cycleCorrect. Cycles prevent any valid topological order.

That BFS visits every node twiceBFS behavior is unrelated to whether the dependency graph is acyclic.

That a set stores the nodesThe container alone does not prove the dependency structure is valid.

Exercises¶

Write four one-line prompts of your own and map each one to the best-fit DSA tool.
Change one answer in the runnable examples so the score drops, then explain what topic that mistake reveals.
Sketch a tiny dependency graph of three tasks and explain whether topological sort is valid.

Key Takeaway¶

This checkpoint is meant to feel fast and decisive. If you can classify short prompts accurately, you are ready to move beyond review and start learning algorithm-design strategies.

The next notebook, greedy_algorithms, will ask a harder question: once you know the right data structure, how do you make a sequence of smart local choices that leads toward a strong overall solution?

answer_key = {
    "undo feature": "stack",
    "fewest hops": "bfs",
    "dependency order": "topological sort",
    "weighted cheapest route": "dijkstra",
}

learner_attempt = {
    "undo feature": "stack",
    "fewest hops": "bfs",
    "dependency order": "topological sort",
    "weighted cheapest route": "dijkstra",
}

score = 0
missed_topics = []

for prompt, expected in answer_key.items():
    actual = learner_attempt[prompt]
    if actual == expected:
        score += 1
    else:
        missed_topics.append(prompt)

print(f"Score: {score}/{len(answer_key)}")
print("Needs review:", missed_topics or "None")

Score: 4/4
Needs review: None