Litgu.ru - Литературный Гуру

Introduction.
What is an algorithm?
Multiplication.
Congressional Apportionment.
A Bad Example.
Describing Algorithms.
Analyzing Algorithms.
Recursion.
Reductions.
Simplify and Delegate.
Tower of Hanoi.
Mergesort.
Quicksort.
The Pattern.
Recursion Trees.
Linear-Time Selection.
Fast Multiplication.
Exponentiation.
Backtracking.
N Queens.
Game Trees.
Subset Sum.
The General Pattern.
Text Segmentation (Interpunctio Verborum).
Longest Increasing Subsequence.
Longest Increasing Subsequence, Take 2.
Optimal Binary Search Trees.
Dynamic Programming.
Matravr.
Aside: Even Faster Fibonacci Numbers.
Interpunctio Verborum Redux.
The Pattern: Smart Recursion.
Warning: Greed is Stupid.
Longest Increasing Subsequence.
Edit Distance.
Subset Sum.
Optimal Binary Search Trees.
Dynamic Programming on Trees.
Greedy Algorithms.
Storing Files on Tape.
Scheduling Classes.
General Pattern.
Huffman Codes.
Stable Matching.
Basic Graph Algorithms.
Introduction and History.
Basic Definitions.
Representations and Examples.
Data Structures.
Whatever-First Search.
Important Variants.
Graph Reductions: Flood Fill.
Depth-First Search.
Preorder and Postorder.
Detecting Cycles.
Topological Sort.
Memoization and Dynamic Programming.
Strong Connectivity.
Strong Components in Linear Time.
Minimum Spanning Trees.
Distinct Edge Weights.
The Only Minimum Spanning Tree Algorithm.
Borůvka’s Algorithm.
Jarník’s (“Prim’s”) Algorithm.
Kruskal’s Algorithm.
Shortest Paths.
Shortest Path Trees.
Negative Edges.
The Only SSSP Algorithm.
Unweighted Graphs: Breadth-First Search.
Directed Acyclic Graphs: Depth-First Search.
Best-First: Dijkstra’s Algorithm.
Relax ALL the Edges: Bellman-Ford.
All-Pairs Shortest Paths.
Introduction.
Lots of Single Sources.
Reweighting.
Johnson’s Algorithm.
Dynamic Programming.
Divide and Conquer.
Funny Matrix Multiplication.
(Kleene-Roy-)Floyd-Warshall(-Ingerman).
Maximum Flows & Minimum Cuts.
Flows.
Cuts.
The Maxflow-Mincut Theorem.
Ford and Fulkerson’s augmenting-path algorithm.
Combining and Decomposing Flows.
Edmonds and Karp’s Algorithms.
Further Progress.
Applications of Flows and Cuts.
Edge-Disjoint Paths.
Vertex Capacities and Vertex-Disjoint Paths.
Bipartite Matching.
Tuple Selection.
Disjoint-Path Covers.
Baseball Elimination.
Project Selection.
NP-Hardness.
A Game You Can’t Win.
P versus NP.
NP-hard, NP-easy, and NP-complete.
Formal Definitions (HC SVNT DRACONES).
Reductions and Sat.
3Sat (from CircuitSat).
Maximum Independent Set (from 3Sat).
The General Pattern.
Clique and Vertex Cover (from Independent Set).
Graph Coloring (from 3Sat).
Hamiltonian Cycle.
Subset Sum (from Vertex Cover).
Other Useful NP-hard Problems.
Choosing the Right Problem.
A Frivolous Real-World Example.
On Beyond Zebra.
Index.
Index of People.
Index of Pseudocode.