 Название: Algorithms
Автор: Erickson Jeff
Издательство: Independently published
Год: 2019
Страниц: 472
Язык: английский
Формат: pdf (true)
Размер: 23.9 MB
Algorithms are the lifeblood of computer science. They are the machines that proofs build and the music that programs play. Their history is as old as mathematics itself. This textbook is a wide-ranging, idiosyncratic treatise on the design and analysis of algorithms, covering several fundamental techniques, with an emphasis on intuition and the problem-solving process. The book includes important classical examples, hundreds of battle-tested exercises, far too many historical digressions, and exaclty four typos.
The book web site also contains several hundred pages of additional lecture notes on related and more advanced material, as well as a near-complete archive of past homeworks, exams, discussion/lab problems, and other teaching resources.
Contents:
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.
Скачать Algorithms (2019)
|
Разделы сайта
Авторизация
Реклама
Algorithms (2019) 
