Lukas ShaghashviliMental math ↗
Made while learning / ITU

Ideas you can
play with.

Three courses, one playground. Change an input, run an example, and follow what happens.

01 / ITU · SWU

Algoritmer og datastrukturer

Build the foundations: how we organise data, compare solutions, and reason about the work an algorithm does.

Reading & course references

Robert Sedgewick & Kevin Wayne · Algorithms, 4th edition (2011). Weekly topics from my SWU course, with Sedgewick & Wayne as the main reference. These examples expose the data structure and its cost model. The links also reuse graph traversal and trie tools from the wider playground.

Union-findWeek 1 · §1.5 · Union-findBuild connected components one pair at a time.Fixed-length sequencesFundamentals · §1.1Read and replace an array slot by index.Stacks & queuesWeek 3 · §1.3Compare last-in-first-out and first-in-first-out removal.Analysis of algorithmsWeek 4 · §1.4Compare scan, pair enumeration and binary-search costs.SortingWeek 5 · §2.1–2.2 · Sorting & mergesortCompare adjacent exchanges with merging sorted runs.Priority queuesWeek 6 · §2.4Build a min-heap, then repeatedly extract the minimum.Graph theory, DFS & BFSWeek 7 · Ch. 4Explore reachability, traversal order and directed acyclic graphs.Dijkstra’s shortest pathsWeek 8 · §4.4Relax weighted edges from a source to every vertex.Binary searchSearching · §1.1, §3.1Halve the remaining search interval after each comparison.Symbol tables & hashingWeek 9 · §3.4Resolve collisions with separate chaining.Binary search treesWeek 10 · §3.2Insert keys and follow a search path through the tree.Tries & prefix searchWeek 10 · §5.2Store words by sharing their common prefixes.QuicksortWeek 11 · §2.3Partition around a pivot, then sort the two sides.String radix sortWeek 11 · §5.1Sort equal-length words one character at a time.Amortized array growthWeek 11 · §1.3–1.4See occasional resizing costs spread across appends.Minimum spanning treesWeek 13 · §4.3Use Kruskal’s algorithm to connect all vertices cheaply.
02 / ITU · SWU

Distributed Systems

Several machines, no shared clock. Explore what messages tell us, what failures hide, and how replicas agree on a result.

Reading & course references

Coulouris, Dollimore, Kindberg & Blair · Distributed Systems: Concepts and Design, 5th edition. Coulouris et al. is the main reference, supported by the weekly Go lectures. Each simulation states its timing, delivery and failure assumptions. Raft follows the course lecture supplement.

Go concurrencyWeek 2 · Go concurrency lectureCompare a lost update with a mutex-protected increment.Reliable deliveryWeek 4 · Ch. 3–4 · NetworkingRecover from lost data or a lost acknowledgement.RPC retriesWeek 5 · Ch. 5 · Remote invocationSee why a lost reply makes retries ambiguous.Physical clock synchronizationWeek 6 · §14.3 · Physical clocksEstimate server time and expose delay asymmetry.Logical clocks§14.4 · Logical time and logical clocksCompare Lamport timestamps with vector clocks.Distributed mutual exclusionWeek 9 · §15.2 · Mutual exclusionQueue requests and grant one process access at a time.Leader electionWeek 9 · §15.3 · ElectionsFind the highest live process with the bully algorithm.Byzantine agreementWeek 10 · §15.5 · AgreementRelay conflicting reports before deciding.Consistency during a partitionWeek 10 · CAP lecture; Ch. 18 · ReplicationCompare a blocked write with a stale read.Replication quorums§18.5.5 · Quorum consensus methodsSee why reads and writes need overlapping replica sets.Raft election & replicationWeek 13 · Raft lecture supplementElect a leader, replicate an entry and commit with a majority.
03 / ITU · SWU

Algorithmic Problem Solving

Combine techniques, compare approaches and explore the geometry, graphs and data structures behind a solution.

Reading & course references

Practice tools for the Algorithmic Problem Solving course. Related structures also appear in Algoritmer og datastrukturer; shared tools use the same implementation.

Search & optimisation

SubsetsTechniqueEnumerate every subset of a set.N-QueensProblemPlace queens so none share a row, column or diagonal.Coins & schedulingTechniqueChoose locally useful steps for coins or compatible intervals.Meet in the middleTechniqueFind subsets whose values add to a target.Dynamic programmingTechniqueReuse smaller answers to solve knapsack or exact change.

Graphs & networks

Graph traversalAlgorithmExplore reachability and ordering in a graph.Maximum flowAlgorithmSend as much flow as possible from source to sink.

Geometry & spatial problems

Convex hullAlgorithmFind the outer boundary of a set of points.Polygon areaFormulaMeasure the signed area inside an ordered polygon.OrientationPredicateDecide which side of a directed line a point lies on.Grid proximityProblemFind nearby pairs using a spatial grid.Rotating calipersAlgorithmFind the farthest pair of points on a convex hull.

Data structures & range queries

Segment treeData structureCombine values over a range while supporting updates.Fenwick treeData structureMaintain prefix sums with point additions.Square-root decompositionData structureAnswer range queries by grouping values into blocks.TrieData structureStore words by sharing common prefixes.

Strings & matching

String hashingTechniqueMap text to numbers and update hashes as a window moves.Longest repeated substringProblemFind the longest substring that appears more than once.

Probability & estimation

MinHashEstimatorEstimate how much two sets overlap.Monte CarloEstimatorEstimate area by sampling points in a unit square.