Advanced~6h

Algorithm Analysis Drills

The procedures, until they are fast

CS305 teaches each of these once, against one example, and moves on. This is the volume — thirty-three procedures from the master theorem to a Buss kernel, on questions generated fresh that never run out. Each stays green only while your recent answers hold it there.

Start this project See the modules

Modules: 8
Drills: 33
Build steps: 0
Time: ~6h

Walk out able to

Name a master-theorem case, add up a cut, and fill a failure function — without stopping to rebuild the method first.

What you drill

Recurrences and cost

Master theorem, recursion trees, amortized cost.

Greedy and flow

Rules that are provable, matroids, cuts, circulations.

Strings and geometry

Failure functions, rolling hashes, orientation, hulls.

When exact is too slow

Approximation, competitive and parameterized bounds.

The pitch

What you practise, and what you leave with

Not an artifact — a set of reflexes. Thirty-three procedures that are each either current or not, and a rail that says which.

You will practise

Recurrences, amortized cost, lower bounds
Greedy rules, matroids, scheduling
Flow, cuts, strings, planar predicates
Approximation, online and FPT bounds

Afterwards you can

Name a master-theorem case on sight
Add up a cut and certify a max flow
Fill a failure function without pausing
Tell an FPT bound from an XP one

Modules

8 modules, 35 items

Lessons explain one idea. Drills repeat it until it sticks. Build steps make something that exists afterwards.

1
Solve a recurrence
~42 min
Name the case, read off the bound, and count what a recursion tree holds.
- LessonWhat this project is for4 min
- DrillName the master-theorem case9 min
- DrillRead off the bound10 min
- DrillCount what a recursion tree holds10 min
- DrillUnroll a recurrence to a term9 min
2
Amortize a sequence
~30 min
Total a run of operations, track a potential, and say what the bound guarantees.
- DrillTotal a run of operations11 min
- DrillTrack a potential across one step10 min
- DrillSay what the bound guarantees9 min
3
Bound it from below
~31 min
Count the comparisons a model forces, and name the argument that forces them.
- DrillCount the forced comparisons11 min
- DrillName the argument, and its model10 min
- DrillRead a randomized guarantee10 min
4
Prove a greedy rule
~1h
Match rule to objective, score it, and know what certifies it as optimal.
- LessonWhat is not graded here6 min
- DrillMatch the rule to the objective10 min
- DrillScore a schedule12 min
- DrillCertify a greedy rule12 min
- DrillBuild and cost a Huffman tree12 min
- DrillFind where greedy loses11 min
5
Route flow, read the cut
~55 min
Add up a cut, push flow to the maximum, and say what the pair certifies.
- DrillAdd up a cut10 min
- DrillPush flow to the maximum14 min
- DrillFind a residual bottleneck12 min
- DrillBalance a circulation9 min
- DrillRead a flow certificate10 min
6
Index a string
~47 min
Fill a failure function, fall back on a mismatch, roll a hash, read a suffix index.
- DrillFill in a failure function11 min
- DrillFall back on a mismatch12 min
- DrillRoll a hash one character11 min
- DrillRead a suffix index13 min
7
Decide with a predicate
~43 min
Take an orientation sign, then scan a hull, classify a pair, and run a sweep.
- DrillTake an orientation sign9 min
- DrillCount the hull vertices13 min
- DrillClassify two segments11 min
- DrillRun a sweep line10 min
8
Settle for a guarantee
~53 min
Compute a ratio, cost an online decision, and place a bound in its class.
- DrillCompute an approximation ratio11 min
- DrillCost an online decision12 min
- DrillName the guarantee10 min
- DrillPlace a bound in its class10 min
- DrillSize a kernel10 min