University of Marburg CS 627
Professor Wild · University of Marburg · 14 lectures with notes
Every lecture with its full transcript and chapters, and one search across all 14 lectures.
Advanced Algorithms (Winter 2026-27) - 03-01 Pseudopolynomial algorithms
Pseudopolynomial algorithms become polynomial-time algorithms when the largest input integer is polynomially bounded.
Advanced Algorithms (Winter 2026-27) - 03-02 Knapsack
Knapsack’s dynamic program is pseudo-polynomial because its table has nB states and capacity B may be exponentially large in its encoding.
Advanced Algorithms (Winter 2026-27) - 03-03 Knapsack DP solution
Knapsack has complementary dynamic programs indexed by capacity or exact value, each efficient when its indexed quantities are small.
Advanced Algorithms (Winter 2026-27) - 03-04 Strong NP hardness
Strong NP-hardness captures problems that remain NP-hard with small numbers, ruling out pseudo-polynomial algorithms unless P = NP.
Advanced Algorithms (Winter 2026-27) - 04-01 Parameterized Problems
Parameterized complexity measures problem difficulty by a chosen value, such as solution size, rather than input size alone.
Advanced Algorithms (Winter 2026-27) - 04-02 Fixed Parameter Tractability
FPT algorithms allow exponential dependence on a small parameter while keeping input-size dependence polynomial, but only meaningful parameters make the guarantee useful.
Advanced Algorithms (Winter 2026-27) - 04-03 Depth-Bounded Search I
Branching on an uncovered edge yields a Vertex Cover algorithm with search depth K and at most 2^K leaves.
Advanced Algorithms (Winter 2026-27) - 04-04 Kernelization
Kernelization is equivalent to fixed-parameter tractability, with Vertex Cover offering a concrete O(K²) kernel.
Advanced Algorithms (Winter 2026-27) - 04-05 Kernel for p-MaxSat
Canonical p-MaxSat has an O(K²)-size kernel, establishing fixed-parameter tractability in the target K.
Advanced Algorithms (Winter 2026-27) - 04-06 Depth-Bounded Search for Planar Independent Set
Planar graphs are 5-degenerate, enabling a depth-K search with at most six branches per level for independent set.
Advanced Algorithms (Winter 2026-27) - 04-07 Depth-Bounded Search for Closest String
A K-depth search solves Closest String by branching on K+1 mismatches, giving an O(K^K)-size search tree.
Advanced Algorithms (Winter 2026-27) - 04-08 Correctness for Closest String FPT
Branching on k + 1 mismatches preserves correctness for the p-closest string search, with a search space of roughly k^k.
Advanced Algorithms (Winter 2026-27) - 04-09 Linear Recurrences
Solving low-degree cases cuts the vertex-cover search bound to about 1.4656^k, analyzed through characteristic roots.
Advanced Algorithms (Winter 2026-27) - 04-10 Interleaving
Interleaving kernelization with branching can prune recursive searches early, though its worst-case benefit depends on the recurrence and reduction cost.