Midterm 2: Learn from Zero

Content locked

The catalog is public. Reading this content requires approved access.

1. Start here

Before graphs: Big-O and proofs in plain English

A refresher on the data structures we actually use

2. Graphs: the small amount of vocabulary you need

Trace BFS once

Question 1: Fewest edges versus least weight

3. Shortest paths: estimates that improve

Relaxation is the shared operation

Dijkstra: finalize the cheapest unfinished vertex

Bellman–Ford: allow improvements to travel farther

Trace Bellman–Ford without confusing passes

Choose the algorithm from its assumptions

Question 2: Break the finalization rule

4. Modeling: change the graph to fit the question

Entry tolls: change edge weights

Multiple starting locations: add one source

A budget: expand the state

Why the extra state is necessary: a tiny budget example

Question 3: One free flight

5. MSTs: connect everything as cheaply as possible

Trace both algorithms

The cut picture explains correctness

Question 4: Repair a tree after adding an edge

6. Greedy: make a choice, then prove it is safe

Interval scheduling: earliest finish leaves room

Fixed-order packing: compare progress

What an exam-length greedy proof looks like

Question 5: Find the failed greedy rule

7. Flow: send units through constrained routes

Residual edges tell you what can change

Watch a reverse edge rescue an assignment

Why no residual path means maximum

Runtime and integrality

Question 6: Residual capacity and cuts

8. Flow reductions: make each constraint visible

A complete reduction has two directions

Two construction tools

Question 7: Jobs with department quotas

9. Second pass: complete the lecture coverage

Johnson: make negative edges safe for Dijkstra

Other MST and greedy patterns

Work the scheduling ratio instead of memorizing it

Build a Huffman tree by hand

See Johnson’s cancellation numerically

More flow applications

Work a project-selection cut

10. Learn the exam’s problem families

Family A: A familiar shortest-path algorithm with a changed condition

Family B: Hide an extra condition inside the graph

Family C: An MST claim or a local update

Family D: Invent or reject a greedy rule

Family E: A story about assigning limited resources

Family F: Trace flow, explain a failure, or certify optimality

A complete answer skeleton

10A. Three-hour study blocks

10B. Move from the guide to instructor problems

11. Closed-note readiness check

Question 8: Choose and justify

Question 9: Design from a blank page

Question 10: Negative cycles do not poison everything

Question 11: Cut direction and optimality

Question 12: Prove or disprove an MST claim

Question 13: Retrieve the second-pass ideas

12. Turn your results into the next study block