Advanced -> Randomized Algorithms¶

Monte Carlo and Las Vegas design, amplification, randomized rounding, and probability-backed correctness guarantees.

Microtopics¶

Source	Type
MIT OCW 6.856J lecture notes	`Course`
CMU 15-359 Probability and Computing	`Course`

Material	Type
Hashing tutorial	`repo case study`
Hashing ladder	`adjacent ladder`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Problem Set 1	`UT Austin CS388R`	`Theory`	-	-	-	Min-Cut; Sampling; Expected Complexity	A strong theory-first warmup on randomized design and analysis from an algorithms course.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Problem with Random Tests	`Codeforces`	`Hard`	-	Probabilistic Reasoning	Expected Value; Randomized Thinking	Probability; Adversarial Tests	A direct fit for understanding how random testing interacts with algorithm design.
Wizards and Huge Prize	`Codeforces`	`Hard`	-	Probabilistic Model	Probability Basics	Probability; Randomization; Expected Value	A classic probability-heavy contest problem.
Gosha is hunting	`Codeforces`	`Very Hard`	-	Stochastic Analysis	Probability; DP	Probability; Randomization; Expected Value	A high-end probabilistic problem that rewards careful randomized analysis.
Isaac's Queries	`Codeforces`	`Very Hard`	-	Interactive Reasoning	Probability; Interactive Protocols	Probability; Interactive	A modern hard problem where randomness and interaction both matter.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Journey	`Codeforces`	`Medium`	Tree Expectation, Expected Value	DFS Expectation	Tree DFS; Basic Probability	Tree DFS; Probability	A friendly bridge from tree DFS into expectation, best framed here as cross-topic probability practice.
Control of Randomness	`Codeforces`	`Hard`	Probability On Trees, Tree DP	Tree DP; Case Analysis	Basic Probability	Probability; Expected Process	Better treated as a cross-topic probability-on-trees exercise than as a pure randomized-design core problem.
I Love Balls	`Codeforces`	`Hard`	Probability DP, Expected Value	State Expectation	Basic Probability; DP States	Game Process	A strong cross-topic expectation/DP problem that supports randomized-thinking practice without being a randomized-design essential.
Expected Value Again	`Codeforces`	`Very Hard`	Combinatorial Expectation, Expected Value	Counting; Expectation Analysis	Basic Probability; Combinatorics	Combinatorics	A very hard cross-topic expectation/combinatorics exercise rather than a primary randomized-algorithms core item.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`FINDINGBORDERS`	Finding Borders	`secondary`	`easy`	rolling hash; prefix-suffix equality; proper borders enumeration	Note	Code

python3 scripts/generate_problem_catalog.py