Encyclopedia of Algorithms, Second Edition
- 75h 36m
- Ming-Yang Kao
- Springer
- 2016
This dynamic reference work provides solutions to vital algorithmic problems for scholars, researchers, practitioners, teachers and students in fields such as computer science, mathematics, statistics, biology, economics, financial software, and medical informatics.
This second edition is broadly expanded, building upon the success of its former edition with more than 450 new and updated entries. These entries are designed to ensure algorithms are presented from growing areas of research such as bioinformatics, combinatorial group testing, differential privacy, enumeration algorithms, game theory, massive data algorithms, modern learning theory, social networks, and VLSI CAD algorithms.
Over 630 entries are organized alphabetically by problem, with subentries allowing for distinct solutions. Each entry includes a description of the basic algorithmic problem; the input and output specifications; key results; examples of applications; citations to key literature, open problems, experimental results, links to data sets and downloadable code.
All entries are peer-reviewed, written by leading experts in the field—and each entry contains links to a summary of the author’s research work.
About the Author
Ming-Yang Kao is Professor of Computer Science at the Northwestern University, Evanston. He got a B.S. in Mathematics, 1978 at the National Taiwan University, Republic of China (Taiwan) and his Ph.D. in Computer Science, 1986, at Yale University, USA.
Prof. Kao studies the design, analysis and implementation of algorithms. His work spans a broad range of applications including bioinformatics, computational finance, electronic commerce, and nanotechnology. Kao's most recent research includes work on DNA self-assembly, variants of the traveling salesman problem, and graph labeling problems.
Kao heads the EECS Computing, Algorithms & Applications Division and is the editor-in-chief of Algorithmica.
In this Book
-
A: Abelian Hidden Subgroup Problem — Automated Search Tree Generation
-
B: Backdoors to SAT — Byzantine Agreement
-
C: Cache-Oblivious B-Tree — Curve Reconstruction
-
D: Data Migration — Dynamic Trees
-
E: Edit Distance under Block Operations — External Sorting and Permuting
-
F: Facility Location — Fully Dynamic Transitive Closure
-
G: Gate Sizing — Greedy Set-Cover Algorithms
-
H: Hamilton Cycles in Random Intersection Graphs — Hierarchical Space Decompositions for Low-Density Scenes
-
I: I/O-Model — Intrinsic Universality in Self-Assembly
-
J: Jamming-Resistant MAC Protocols for Wireless Networks
-
K: k-Best Enumeration — Knowledge in Distributed Systems
-
L: Large-Treewidth Graph Decompositions — LP Decoding
-
M: Majority Equilibrium — Musite: Tool for Predicting Protein Phosphorylation Sites
-
N: Nash Equilibria and Dominant Strategies in Routing — Nucleolus
-
O: O(log log n)-Competitive Binary Search Tree — Orthogonal Range Searching on Discrete Grids
-
P: P2P — Prophet Inequality and Online Auctions
-
Q: Quadtrees and Morton Indexing — Quorums
-
R: Radiocoloring in Planar Graphs — Rumor Blocking
-
S: Schedulers for Optimistic Rate Based Flow Control — Synchronizers, Spanners
-
T: Table Compression — Two-Interval Pattern Problems
-
U: Undirected Feedback Vertex Set — Utilitarian Mechanism Design for Single-Minded Agents
-
V: Vector Bin Packing — Voronoi Diagrams and Delaunay Triangulations
-
W: Wait-Free Synchronization — Work-Function Algorithm for k-Servers
-
List of Entries
