Weeks 35–36 and beyond · About 20 hours, then ongoing

Optional depth

Specialised structures and ideas worth knowing about. Treat this as a menu, not a checklist.

Only come here once the previous stage is genuinely solid. Nothing below is needed for most engineering work, and chasing all of it is a common way to feel busy without getting better.

Why this stage exists

Two things here have real everyday value: knowing that some problems are genuinely unsolvable at scale, and knowing that randomised approaches exist. The rest is depth for its own sake, which is fine as long as you know that is what it is.

What you are learning — 5 topics

Segment trees and Fenwick trees

Structures that answer questions like “what do items 300 to 900 add up to?” quickly, even while the data keeps changing.

A answers range questions instantly but has to be rebuilt whenever a value changes. These structures accept slightly slower queries in exchange for cheap updates, which is the right trade when data is live.

A Fenwick tree is remarkably compact — about ten lines — but the index arithmetic is genuinely unintuitive. A segment tree is longer and much easier to reason about.

Rarely needed outside competitive programming. Worth knowing the name and the shape of the problem they solve, so you recognise it if it ever turns up.

What it costsBoth give range queries and O(log n) updates.

Where you meet it in real softwareLive analytics dashboards, leaderboards, range totals over data that keeps changing.

Go and read

CP-Algorithms: segment treeDocsThe thorough treatment. Long, and correct.cp-algorithms.com/data_structures/segment_tree.html CP-Algorithms: Fenwick treeDocsThe compact alternative.cp-algorithms.com/data_structures/fenwick.html

String search algorithms

Finding a piece of text inside a much larger piece of text, without re-checking things you already know.

The obvious approach compares the pattern against every position, which repeats work whenever a partial match fails. KMP precomputes a table of where to resume after a failure, so it never re-examines the same character.

Rabin-Karp takes a different route: it hashes the pattern and compares hashes as it slides along, which makes searching for many patterns at once cheap.

These are what make tools like grep fast on large files.

What it costsO(text length + pattern length), rather than the naive O(text × pattern).

Where you meet it in real softwaregrep and text search, plagiarism detection, DNA sequence matching.

Go and read

CP-Algorithms: prefix function and KMPDocsThe clearest correct explanation of the failure table.cp-algorithms.com/string/prefix-function.html GeeksforGeeks: KMPDocsA gentler walkthrough with diagrams.geeksforgeeks.org/dsa/kmp-algorithm-for-pattern-searching

Network flow

Working out the maximum that can move through a network whose connections each have a capacity limit.

Picture water pipes of differing widths. The question is how much can flow from source to destination at once, and the answer is limited by bottlenecks rather than by any single pipe.

The surprising part is how many problems that look nothing like plumbing turn out to be this in disguise — particularly matching problems, such as assigning people to jobs where only certain pairings are allowed.

Genuinely specialised. Know it exists and what shape of problem it solves.

Where you meet it in real softwareLogistics, scheduling, assignment and matching problems.

Go and read

CP-Algorithms: Edmonds-KarpDocsThe standard approachable implementation.cp-algorithms.com/graph/edmonds_karp.html

Randomised and approximate algorithms

Using randomness deliberately, or accepting a nearly-right answer, to get something fast enough to be useful.

Quicksort picks its pivot at random specifically so that no particular input ordering can reliably make it slow. Randomness as a defence against worst cases is a genuinely useful idea.

Reservoir sampling picks a fair random sample from a stream of unknown length using constant memory — useful when you cannot hold everything.

A Bloom filter answers “have I seen this before?” using very little memory, at the price of occasional false positives. It never wrongly says no, only sometimes wrongly says yes, and that asymmetry is what makes it usable — it is a cheap first check before an expensive real one.

This is the most practically useful topic in this stage. Approximate answers that fit in memory frequently beat exact answers that do not.

Where you meet it in real softwareSampling large datasets, deduplication at scale, database and cache pre-checks, simulation.

Go and read

GeeksforGeeks: randomized algorithmsDocsOverview with the main techniques.geeksforgeeks.org/dsa/randomized-algorithms

P, NP and what cannot be done quickly

Some problems have no known fast solution, and probably never will. Knowing which ones saves you from trying.

P is the set of problems solvable in reasonable time. NP is the set where, if someone hands you an answer, you can check it quickly — even if finding it is hard. Whether those two sets are actually the same is the most famous open question in computer science.

NP-complete problems are the hardest in NP, and they include very ordinary-sounding things: finding the shortest route visiting a list of cities, or fitting items into a container with no wasted space.

The practical value is knowing when to stop optimising. If your problem is NP-complete, there is no clever waiting to be found, and the right move is to change the question: accept a good-enough answer, use a heuristic, or constrain the input so the hard part goes away. Recognising that early is worth far more than any specific algorithm on this page.

Where you meet it in real softwareRoute planning, scheduling, resource packing — and knowing when to accept an approximation rather than chase an exact answer.

Go and read

GeeksforGeeks: NP-completenessDocsA readable introduction that does not assume a maths degree.geeksforgeeks.org/dsa/introduction-to-np-completeness

Build these yourself

Reading about this stage is not the same as finishing it. Type every one of these from a blank file rather than copying — the writing is the part that teaches.

Build a Bloom filter

Use several hash functions over a block of bits. Add a thousand items, then test how often it wrongly reports having seen something it has not. Change the size and watch the error rate move. The most practically useful thing in this stage.

Implement KMP

Build the failure table first and make sure you can explain what each entry means before writing the search itself. That table is the whole algorithm.

You are done with this stage when

Exit checkYou can explain why some problems have no fast solution, and what to do instead. Anything else in this stage is optional depth.

If you cannot do this, repeat the stage rather than moving on. Nothing later gets easier by skipping it.

Worth knowing before you start

Do not chase every topic here. Segment trees and network flow are rarely needed outside competitive programming. Extra depth in dynamic programming and graphs pays far more.

This stage corresponds to DSA Phase 6 — Advanced Topics & Consolidation in the source roadmap.