Applied Algorithms,
made to stick before the exam.
Intuition first, then the algorithm, then a worked example you can follow line-by-line. Every metaheuristic and graph problem from the course — explained clearly with interactive visuals.
Foundations
The math behind "is my algorithm fast enough?"
Graph Problems
When the structure of the problem is a graph.
Shortest Path (Dijkstra)
Greedy frontier expansion. Worked through with the exact 9-node example from the course slides.
›Graph Partitioning (Bisection)
Split vertices into two sets, minimize cut edges. External/internal cost, gain of a swap.
›Kernighan–Lin
The "champion" heuristic — chains of swaps instead of one, then keep the prefix with the best gain.
›Multilevel Local Search
Coarsen → optimize at the coarse level → un-coarsen → refine. Scales to huge problems.
Classic Optimization Problems
The benchmark problems every metaheuristic gets tested on.
Traveling Salesman (TSP)
Construction heuristics (random, greedy, RI, CI) then improvement (2-opt, 3-opt). Interactive tour-builder.
›0/1 Knapsack
4 construction methods, 5 local search versions, and why value/weight ratio matters most.
›Transportation Problem
Northwest Corner & Least Cost for an initial solution, then Stepping Stone for the optimum.
›Constraint Satisfaction
Variables, domains, constraints. Min-Conflicts, GSAT, and the multilevel CSP algorithm.
Metaheuristics
General-purpose optimization strategies — work on almost any problem.
Genetic Algorithm
Population → select → crossover → mutate → cull. 1-point and 2-point crossover, full walk-through.
›Selection Methods
Roulette wheel (proportional fitness) and tournament selection — with worked TSP/graph-coloring examples.
›Simulated Annealing
Accept bad moves with probability e−ΔC/T. Cool the temperature slowly. The four parameters explained.
›Memetic Algorithm
Genetic Algorithm + local search on each offspring. Exploration + intensification.
›Kick Method (ILS)
Greedy descent to a local optimum, then "kick" to another basin. Repeat. Iterated Local Search in essence.
›Greedy + Random Hybrid
Like a stripped-down simulated annealing — controlled bad-move acceptance with cooling probability.