Efnisyfirlit

• Half-title
• Title page
• Copyright information
• Contents
• Preface
• 1 Introduction
• 1.1 Programming Competitions
• 1.2 Python in a Few Words
• 1.3 Input-Output
• 1.4 Complexity
• 1.5 Abstract Types and Essential Data Structures
• 1.6 Techniques
• 1.7 Advice
• 1.8 A Problem: `Frosting on the Cake’
• 2 Character Strings
• 2.1 Anagrams
• 2.2 T9—Text on 9 Keys
• 2.3 Spell Checking with a Lexicographic Tree
• 2.4 Searching for Patterns
• 2.5 Maximal Boundaries—Knuth–Morris–Pratt
• 2.6 Pattern Matching—Rabin–Karp
• 2.7 Longest Palindrome of a String—Manacher
• 3 Sequences
• 3.1 Shortest Path in a Grid
• 3.2 The Levenshtein Edit Distance
• 3.3 Longest Common Subsequence
• 3.4 Longest Increasing Subsequence
• 3.5 Winning Strategy in a Two-Player Game
• 4 Arrays
• 4.1 Merge of Sorted Lists
• 4.2 Sum Over a Range
• 4.3 Duplicates in a Range
• 4.4 Maximum Subarray Sum
• 4.5 Query for the Minimum of a Range—Segment Tree
• 4.6 Query the Sum over a Range—Fenwick Tree
• 4.7 Windows with k Distinct Elements
• 5 Intervals
• 5.1 Interval Trees
• 5.2 Union of Intervals
• 5.3 The Interval Point Cover Problem
• 6 Graphs
• 6.1 Encoding in Python
• 6.2 Implicit Graphs
• 6.3 Depth-First Search—DFS
• 6.4 Breadth-First Search—BFS
• 6.5 Connected Components
• 6.6 Biconnected Components
• 6.7 Topological Sort
• 6.8 Strongly Connected Components
• 6.9 2-Satisfiability
• 7 Cycles in Graphs
• 7.1 Eulerian Tour
• 7.2 The Chinese Postman Problem
• 7.3 Cycles with Minimal Ratio of Weight to Length—Karp
• 7.4 Cycles with Minimal Cost-to-Time Ratio
• 7.5 Travelling Salesman
• 7.6 Full Example: Menu Tour
• 8 Shortest Paths
• 8.1 Composition Property
• 8.2 Graphs with Weights 0 or 1
• 8.3 Graphs with Non-negative Weights—Dijkstra
• 8.4 Graphs with Arbitrary Weights—Bellman–Ford
• 8.5 All Source–Destination paths—Floyd–Warshall
• 8.6 Grid
• 8.7 Variants
• 9 Matchings and Flows
• 9.1 Maximum Bipartite Matching
• 9.2 Maximal-Weight Perfect Matching—Kuhn–Munkres
• 9.3 Planar Matching without Crossings
• 9.4 Stable Marriages—Gale–Shapley
• 9.5 Maximum Flow by Ford–Fulkerson
• 9.6 Maximum Flow by Edmonds–Karp
• 9.7 Maximum Flow by Dinic
• 9.8 Minimum s-t Cut
• 9.9 s-t Minimum Cut for Planar Graphs
• 9.10 A Transport Problem
• 9.11 Reductions between Matchings and Flows
• 9.12 Width of a Partial Order—Dilworth
• 10 Trees
• 10.1 Huffman Coding
• 10.2 Lowest Common Ancestor
• 10.3 Longest Path in a Tree
• 10.4 Minimum Weight Spanning Tree—Kruskal
• 11 Sets
• 11.1 The Knapsack Problem
• 11.2 Making Change
• 11.3 Subset Sum
• 11.4 The k-sum Problem
• 12 Points and Polygons
• 12.1 Convex Hull
• 12.2 Measures of a Polygon
• 12.3 Closest Pair of Points
• 12.4 Simple Rectilinear Polygon
• 13 Rectangles
• 13.1 Forming Rectangles
• 13.2 Largest Square in a Grid
• 13.3 Largest Rectangle in a Histogram
• 13.4 Largest Rectangle in a Grid
• 13.5 Union of Rectangles
• 13.6 Union of Disjoint Rectangles
• 14 Numbers and Matrices
• 14.1 GCD
• 14.2 Bézout Coefficients
• 14.3 Binomial Coefficients
• 14.4 Fast Exponentiation
• 14.5 Prime Numbers
• 14.6 Evaluate an Arithmetical Expression
• 14.7 System of Linear Equations
• 14.8 Multiplication of a Matrix Sequence
• 15 Exhaustive Search
• 15.1 All Paths for a Laser
• 15.2 The Exact Cover Problem
• 15.3 Problems
• 15.4 Sudoku
• 15.5 Enumeration of Permutations
• 15.6 Le Compte est Bon
• 16 Conclusion
• 16.1 Combine Algorithms to Solve a Problem
• 16.2 For Further Reading
• 16.3 Rendez-vous on tryalgo.org
• Debugging tool
• References
• Index