piatra . institutepathwaysFinding the next step…
Connect correctness, asymptotic cost, data structures and trade-offs with executable experiments.
No subject-specific background required; work through the opening foundation.
A search and indexing tool with a correctness argument and benchmark analysis.
Start here if the background is new. Equivalent experience is enough.
Use functions, tests and small programs to compare algorithm correctness and performance.
Robert Sedgewick · Kevin Wayne · reference
Named section and worked examples
Check reading access
Open the readingRobert Sedgewick · Kevin Wayne · reference
Named section and worked examples
Check reading access
Open the readingAlgorithms: programming model. Trace a small algorithm and state its inputs and outputs.
Algorithms: data abstraction. Specify an abstract data type before implementing it.
Robert Sedgewick · Kevin Wayne · reference
Named section and worked examples
Check reading access
Open the readingRobert Sedgewick · Kevin Wayne · reference
Named section and worked examples
Check reading access
Open the readingAlgorithms: bags, queues, stacks. Choose a structure based on required operations.
Algorithms: analysis. Compare an operation count with a timed experiment.
A loop visits every pair of items in a list of n items, including an item paired with itself. How many pairs are visited, and what happens when n doubles?
For each of n first items, count the possible second items.
There are n × n = n² ordered pairs. Doubling n produces (2n)² = 4n² pairs. For n = 10 there are 100 visits; for n = 20 there are 400. This counts the loop’s work, not a guaranteed wall-clock time.
What to look for
Common mistake: Predicting twice as much work because the input size only doubles.
Start this pathway to keep your answers in My learning.
Robert Sedgewick · Kevin Wayne · reference
Named section and worked examples
Check reading access
Open the readingRobert Sedgewick · Kevin Wayne · reference
Named section and worked examples
Check reading access
Open the readingRobert Sedgewick · Kevin Wayne · reference
Named section and worked examples
Check reading access
Open the readingAlgorithms: elementary sorts. Prove why the sorted prefix stays sorted.
Algorithms: mergesort. Derive a recurrence and inspect extra memory.
Algorithms: undirected graphs. Use BFS and DFS on the same graph.
You want binary search to return the first occurrence of 4 in [2, 4, 4, 9]. What must the algorithm do after finding a match, and which cases should you test?
A match proves that an occurrence exists; it does not prove it is the first.
After a match, retain its index and continue searching the left half for an earlier match. With zero-based indexing the required result here is 1. Test an empty list, an absent value, a single match, repeated matches and a match at either end. The input must meet the sorted-order precondition.
What to look for
Common mistake: Returning the first match the search happens to find, or using binary search on unsorted data.
Start this pathway to keep your answers in My learning.
Robert Sedgewick · Kevin Wayne · reference
Named section and worked examples
Check reading access
Open the readingRobert Sedgewick · Kevin Wayne · reference
Named section and worked examples
Check reading access
Open the readingAlgorithms: quicksort. Test partition invariants and adversarial inputs.
Algorithms: hash tables. Inspect collision handling and load factor.
One run of algorithm A takes 0.8 seconds and B takes 1.0 second. Is that enough to conclude A is always faster? Explain a better comparison.
Consider input size, input shape, repeated measurements and correctness.
No. Use identical inputs and an equivalent output contract, repeat measurements, and compare several sizes and input patterns. Verify correctness first and state the execution environment. Report the measured range and the operation-growth argument rather than turning one timing into a universal claim.
What to look for
Common mistake: Treating a single timing or a faster incorrect result as decisive.
Start this pathway to keep your answers in My learning.
Editorial perspectives based on selected works, rather than author-endorsed reading lists.
An editorial comparison of the core argument, alternative explanations and practical evidence.
A curated synthesis cannot be neutral or exhaustive. Follow the primary sources when an interpretation matters.
An editorial route that starts with working examples.
The order supports a particular study method; it does not establish which account is true.
An editorial route that starts with competing explanations.
The order supports a particular study method; it does not establish which account is true.
Background, different viewpoints, and further reading.
Trace a small algorithm and state its inputs and outputs.
Named section and worked examples
Specify an abstract data type before implementing it.
Named section and worked examples
Choose a structure based on required operations.
Named section and worked examples
Compare an operation count with a timed experiment.
Named section and worked examples
Maintain an invariant for dynamic connectivity.
Named section and worked examples
Prove why the sorted prefix stays sorted.
Named section and worked examples
Derive a recurrence and inspect extra memory.
Named section and worked examples
Test partition invariants and adversarial inputs.
Named section and worked examples
Implement and check a heap invariant.
Named section and worked examples
Explain how an application changes the choice of sort.
Named section and worked examples
Define lookup and update behaviour.
Named section and worked examples
Measure the effect of tree shape.
Named section and worked examples
Trace rotations while preserving order.
Named section and worked examples
Inspect collision handling and load factor.
Named section and worked examples
Use BFS and DFS on the same graph.
Named section and worked examples
Find a topological order or a cycle.
Named section and worked examples
Explain the cut property on a small graph.
Named section and worked examples
Compare weighted and unweighted path problems.
Named section and worked examples
Benchmark a pattern search and inspect worst cases.
Named section and worked examples
Construct a mapping that preserves an answer.
Named section and worked examples
Use algorithm traces and correctness arguments before studying recognisers and reductions.