Analysis of algorithms

Table of Contents

Chapter 1 Analysis Basics

• 1.1 What is Analysis?
• 1.2 What to Count and Consider
• 1.3 Mathematical Background
• 1.4 Rates of Growth
• 1.5 Divide and Conquer Algorithms
• 1.6 Recurrence Relations
• 1.7 Analyzing Programs

Chapter 2

• Searching and Selection Algorithms
• 2.1 Sequential Search
• 2.2 Binary Search
• 2.3 Selection
• 2.4 Programming Exercise

Chapter 3

• Sorting Algorithms
• 3.1 Insertion Sort
• 3.2 Bubble Sort
• 3.3 Shellsort
• 3.4 Radix Sort
• 3.5 Heapsort
• 3.6 Merge Sort
• 3.7 Quicksort
• 3.8 External Polyphase Merge Sort
• 3.9 Additional Exercises
• 3.10 Programming Exercises

Chapter 4

• Numeric Algorithms
• 4.1 Calculating Polynomials
• 4.2 Matrix Multiplication
• 4.3 Linear Equations

Chapter 5

• Matching Algorithms
• 5.1 String Matching
• 5.2 Approximate String Matching
• 5.3 Programming Exercises

Chapter 6

• Graph Algorithms
• 6.1 Graph Background and Terminology
• 6.2 Data Structure Methods for Graphs
• 6.3 Depth-First and Breadth-First Traversal†Algorithms
• 6.4 Minimum Spanning Tree Algorithm
• 6.5 Shortest-Path Algorithm
• 6.6 Biconnected Component Algorithm
• 6.7 Partitioning Sets
• 6.8 Programming Exercises

Chapter 7

• Parallel Algorithms
• 7.1 Parallelism Introduction
• 7.2 The PRAM Model
• 7.3 Simple Parallel Operations
• 7.4 Parallel Searching
• 7.5 Parallel Sorting
• 7.6 Parallel Numerical Algorithms
• 7.7 Parallel Graph Algorithms

Chapter 8 Nondeterministic Algorithms

• 8.1 What is NP?
• 8.2 Typical NP Problems
• 8.3 What Makes Something NP?
• 8.4 Testing Possible Solutions

Chapter 9

• Other Algorithmic Techniques
• 9.1 Greedy Approximation Algorithms
• 9.2 Probabilistic Algorithms
• 9.3 Dynamic Programming
• 9.4 Programming Exercises

• Appendix A Random Number Table
• Appendix B Pseudorandom Number Generation
• Appendix C Results of Chapter Study Suggestion
• Appendix D References
• Index