Algorithms

Description

The leading introduction to computer algorithms in use today, including fifty algorithms every programmer should know Princeton Computer Science professors, Robert Sedgewick and Kevin Wayne, survey the most important computer algorithms in use and of interest to anyone working in science, mathematics, and engineering, and those who use computation in the liberal arts. They provide a full treatment of data structures and algorithms for key areas that enable you to confidently implement, debug, and put them to work in any computational environment. Fundamentals Basic programming modelsData abstractionBags, queues, and stacksAnalysis of algorithms Sorting Elementary sortsMergesortQuicksortPriority queuesApplications Graphs Undirected graphsDirected graphsMinimum spanning treesShortest paths Strings String sortsTriesSubstring searchRegular expressionsData compression These algorithms are generally ingenious creations that, remarkably, can each be expressed in just a dozen or two lines of code. As a group, they represent problem-solving power of amazing scope. They have enabled the construction of computational artifacts, the solution of scientific problems, and the development of commercial applications that would not have been feasible without them. Cover Title Page Copyright Page Contents Preface 1. Fundamentals 1.1 Basic Programming Model Primitive data types Loops and conditionals Arrays Static methods Recursion APIs Strings Input and output Binary search 1.2 Data Abstraction Objects Abstract data types Implementing ADTs Designing ADTs 1.3 Bags, Queues, and Stacks APIs Arithmetic expression evaluation Resizing arrays Iterators Linked lists 1.4 Analysis of Algorithms Running time Order-of-growth classifications 1.5 Case Study: Union–Find Dynamic connectivity Quick find Quick union Weighted quick union 2. Sorting 2.1 Elementary Sorts Rules of the game Selection sort Insertion sort Shellsort 2.2 Mergesort Abstract in-place merge Top-down mergesort Bottom-up mergesort 2.3 Quicksort 2.4 Priority Queues Priority queue API Elementary implementations Binary heap Heapsort 2.5 Applications Comparators Stability Median and order statistics 3. Searching 3.1 Symbol Tables Symbol table API Ordered symbol table API Sequential search Binary search 3.2 Binary Search Trees Basic implementation Order-based methods Deletion 3.3 Balanced Search Trees 2-3 search trees Red–black BSTs Deletion 3.4 Hash Tables Hash functions Separate chaining Linear probing 3.5 Applications Set data type Whitelist and blacklist filters Dictionary lookup Inverted index File indexing Sparse matrix-vector multiplication 4. Graphs 4.1 Undirected Graphs Glossary Undirected graph type Adjacency-lists representation Depth-first search Breadth-first search Connected components Degrees of separation 4.2 Directed Graphs Glossary Digraph data type Depth-first search Strong connectivity Kosaraju–Sharir algorithm Transitive closure 4.3 Minimum Spanning Trees Cut property Greedy algorithm Edge-weighted graph data type Prim's algorithm Kruskal's algorithm 4.4 Shortest Paths Properties of shortest paths Edge-weighted digraph data types Generic shortest paths algorithm Dijkstra's algorithm Shortest paths in edgeweighted DAGs Critical-path method Bellman–Ford algorithm Negative cycle detection Arbitrage 5. Strings 5.1 String Sorts Key-indexed counting LSD string sort MSD string sort 3-way string quicksort 5.2 Tries String symbol table API R-way tries Ternary search tries 5.3 Substring Search Brute–force algorithm Knuth–Morris–Pratt algorithm Boyer–Moore algorithm Rabin-Karp fingerprint algorithm 5.4 Regular Expressions Describing patterns with REs Applications Nondeterministic finite-state automata Simulating an NFA Building an NFA corresponding to an RE 5.5 Data Compression Rules of the game Reading and writing binary data Limitations Run-length coding Huffman compression LZW compression 6. Context Event-Driven Simulation Hard-disc model Collision prediction Collision resolution B-trees Cost model Search and insert Suffix Arrays Suffix sorting Network Flow Ford–Fulkerson algorithm Reductions Sorting Shortest path Bipartite matching Linear programming Intractability Longest-paths problem Boolean satisfiability NP-completeness Index A B C D E F G H I J K L M N O P Q R S T U V W Z Algorithms and Clients