Want to kill it at your job interview in the tech industry? Want to win that coding competition? Learn all the algorithmic techniques and programming skills you need from two experienced coaches, problem setters, and jurors for coding competitions. The authors highlight the versatility of each algorithm by considering a variety of problems and show how to implement algorithms in simple and efficient code. Readers can expect to master 128 algorithms in Python and discover the right way to tackle a problem and quickly implement a solution of low complexity. Classic problems like Dijkstra's shortest path algorithm and Knuth-Morris-Pratt's string matching algorithm are featured alongside lesser known data structures like Fenwick trees and Knuth's dancing links. The book provides a framework to tackle algorithmic problem solving, including: Definition, Complexity, Applications, Algorithm, Key Information, Implementation, Variants, In Practice, and Problems. Python code included in the book and on the companion website.
Author(s): Christoph Dürr, Jill-Jênn Vie
Edition: 1
Publisher: Cambridge University Press
Year: 2021
Language: English
Commentary: Vector PDF
Pages: 264
City: Cambridge, UK
Tags: Algorithms; Data Structures; Python; Graph Algorithms; Linear Algebra; Trees; Algorithm Analysis; Algorithm Complexity; Competitive Programming
Cover
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
