Sara Baase

Indeholder "0. Data Structures and Mathematical Background", "0.1 Miscellaneous Notation and Formulas", "0.2 Some Mathematical Background", " Logarithms", " Probability", " Permutations", " Summation formulas", "0.3 Data Structures", " Notes and references", "1. Analyzing Algorithms: Principles and Examples", "1.1 Introduction", "1.2 The Algorithm Language", "1.3 Analyzing Algorithms", " Correctness", " Amount of work done", " Average and worst-case analysis", " Space Usage", " Simplicity", " Optimality", " Implementation and Programming", "1.4 Searching an Ordered List", " Worst-case analysis", " Average-behavior analysis", " Optimality", "1.5 Finding the Largest and Second Largest Entries in a List", " The tournament method", " Lower bound for finding S", " Implementation of the tournament method for finding M and S", " Time and space requirements", "1.6 Exercises", " Programs", " Notes and references", "2. Sorting", "2.1 Introduction", "2.2 BUBBLESORT", " Worst-case analysis", " Average behaviour", "2.3 QUICKSORT", " The algorithm", " Worst-case", " Average behaviour", " Space usage", " Improvements on the basic Quicksort algorithm", " Remarks", "2.4 Lower Bounds for Sorting by Comparison of Keys", "2.5 HEAPSORT", " Deletion from a heap", " Heap Construction", " Implementation of a heap and the HEAPSORT algorithm", " Worst-case analysis", " Remarks", "2.6 SHELLSORT", " Analysis", "2.7 Bucket Sorts", " Radix sorting", " Analysis", "2.8 Merging Sorted Lists", " Worst case", " Optimality when n=m", " Space usage", " Binary merging", " Worst-case analysis of BINARY MERGE", " Lower bound for merging sorted files", "2.9 External Sorting", " Polyphase merge sorting", " Polyphase merging with three tapes", " Arranging the runs for merging", " Run construction", " Analysis of Algorithm 2.19", " An application: Priority queues", "2.10 Exercises", " Programs", " Notes and references", "3. Graphs and Digraphs", "3.1 Definitions and Representations", " Computer representation of graphs and digraphs", "3.2 A Minimal Spanning Tree Algorithm", " Implementation", " Analyses (time and space)", " Lower Bound", "3.3 A Shortest-path Algorithm", "3.4 Traversing Graphs and Digraphs", " Depth-first and breadth-first search", " Depth-first search and recursion", " Implementation and analysis of depth-first search: Finding connected components of a graph", " Depth-first search trees", "3.5 Biconnected Components of a Graph", " The bicomponent algorithm", " Analysis", " Generalizations", "3.6 Strongly Connected Components of a Digraph", " Implementation, timing, and space usage", "3.7 Exercises", " Programs", " Notes and references", "4 String Matching", "4.1 The Problem and a Straightforward Solution", " Analysis", "4.2 The Knuth-Morris-Pratt Algorithm", " Pattern matching with finite automata", " The Knuth-Morris-Pratt flowchart", " Construction of the KMP flowchart", " Analysis of the flowchart construction", " The KMP scan algorithm", " Remarks and extentions", "4.3 Exercises", " Programs", " Notes and references", "5 Polynomials and Matrices", "5.1 Introductory Comments", "5.2 Evaluating Polynomial Functions", " Horner's method", " Lower bounds for polynomial evaluaion", " Preprocessing of coefficients", " Analysis of polynomial evaluation with preprocessing of coefficients", "5.3 Vector and Matrix Multiplication", " Winograd's matrix multiplication", " Analysis of Winograd's algorithm", " Lower bounds for matrix multiplication", " Strassen's matrix multiplication", "5.4 The Fast Fourier Transform and Convolution", " The discrete Fourier Transform", " Convolution", " Analysis", " Appendix: Complex Numbers and Roots of Unity", "5.5 Exercises", " Programs", " Notes and references", "6 Transitive Closure, Boolean Matrices, and Equivalence Relations", "6.1 The Transitive Closure of a Binary Relation", " Finding the reachability matrix by depth-first search", "6.2 Warshall's Algorithm", " Application of Warshall's algorithm", "6.3 Computing Transitive Closure by Matrix Operations", "6.4 Multiplying Bit Matrices — Kronrod's Algorithm", " Kronrod's algorithm", " Analysis", " Lower bound", " Remarks on transitive closure algorithms", "6.5 Dynamic Equivalence Relations and UNION-FIND Programs", " Implemention", " UNION-FIND programs", " Equivalence programs", " Application - a minimal spanning tree algorithm", " Analysis of Algorithm 6.6", " Other applications", "6.6 Exercises", " Programs", " Notes and references", "7. 'Hard' (NP-Complete) Problems and Approximation Algorithms", "7.1 'Hard' Problems: Definitions, Examples, and Some Properties", " The Class P", " The Class NP", " NP-Complete problems", " What makes a problem hard?", "7.2 Approximation Algorithms", " Measuring the closeness of the approximation", "7.3 The Knapsack Problem", "7.4 Bin Packing", "7.5 Graph Coloring", "7.6 Exercises", " Notes and references", "Bibliography".

Udmærket gennemgang af basale algoritmer fra datalogiens standard værktøjskasse. Nyere versioner af samme bog er meget større og grundigere, så der er ikke rigtigt nogen grund til at holde på denne her.… (más)