Analysis of Algorithms, 2/e

Contents:

Preface

Chapter 1: Analysis Basics • What is Analysis? • Input Classes • Space Complexity • Exercises • What to Count and Consider • Cases to Consider • Exercises • Mathematical Background • Logarithms • Binary Trees • Probabilities • Summations • Exercises • Rates of Growth • Classification of Growth • Exercises • Tournament Method • Lower Bounds • Exercises • Analyzing Programs

Chapter 2: Recursive Algorithms • Analyzing Recursive Algorithms • Exercises • Recurrence Relations • Approximating the Order of a Recurrence Relation • Exercises • Closest Pair • Exercises • Convex Hull • Exercises • Generating Permutations • Exercises • Recursion and Stacks • Programming Exercises

Chapter 3: Searching and Selection Algorithms • Sequential Search • Worst-Case Analysis • Average-Case Analysis • Exercises • Binary Search • Worst-Case Analysis • Average-Case Analysis • Exercises • Selection • Exercises • Programming Exercise

Chapter 4: Sorting Algorithms • Insertion Sort • Worst-Case Analysis • Average-Case Analysis • Exercises • Bubble Sort • Best-Case Analysis • Worst-Case Analysis • Average-Case Analysis • Exercises • Shellsort • Algorithm Analysis • The Effect of the Increment • Exercises • Radix Sort • Analysis • Exercises • Heapsort • Worst-Case Analysis • Average-Case Analysis • Exercises • Merge Sort • MergeLists Analysis • MergeSort Analysis • Exercises • Quicksort • Worst-Case Analysis • Average-Case Analysis • Exercises • External Polyphase Merge Sort • Number of Comparisons in Run Construction • Number of Comparisons in Run Merge • Number of Block Reads • Exercises • Additional Exercises • Programming Exercises

Chapter 5: Numeric Algorithms • Calculating Polynomials • Horner's Method • Preprocessed Coefficients • Exercises • Matrix Multiplication • Winograd's Matrix Multiplication • Strassen's Matrix Multiplication • Exercises • Linear Equations • Gauss?Jordan Method • Exercises

Chapter 6: Formal Language Algorithms • Formal Language Basics • Lexical Ordering • Language Classifications • Exercises • Finite Auomata • Regular Languages • Regular Expression • Regular Grammars • Dererminate and Nondeterministic Finite Automata • Converting a Deterministic Finite Automaton into a Program • Exercises • Designing Finite Automata • Finite Automata Restrictions • Designing a Finite Automaton • Designing a Regular Grammar • Exercises • Finite Automata Equivalence and Limitations • Limits on Finite Automata • Exercises • Pushdown Automata • Creating a Deterministic Pushdown Automaton • Deterministic Context-Free Languages • Nondeterministic Pushdown Automata • Exercises • Context-Free Grammars • Context-Free Grammar Abilities • Designing Context-Free Grammars • Grammar Transformation • Greibach Normal Form • Converting a Context-Free Grammar into a Pushdown Automaton • Exercises • Limitations of Pushdown Automata • Exercises • Programming Language Compilation • Exercises

Chapter 7: Matching Algorithms • String Machine ?Finite Automata • Knuth?Morris?Pratt Algorithm • Boyer?Moore Algorithm • Exercises • Approximate String Matching • Analysis • Exercises • Programming Exercises

Chapter 8: Graph Algorithms • Graph Background and Terminology • Terminology • Exercises • Data Structure Methods for Graphs • The Adjacency Matrix • The Adjacency List • Exercises • Depth-First and Breadth-First Traversal Algorithms • Depth-First Traversal • Breadth-First Traversal • Traversal Analysis • Exercises • Minimum Spanning Tree Algorithm • The Dijkstra?Prim Algorithm • The Kruskal Algorithm • Exercises • Shortest-Path Algorithm • Dijkstra's Algorithm • Exercises • Biconnected Component Algorithm • Exercises • Partitioning Sets • Programming Exercises

Chapter 9: Parallel Algorithms • Parallelism Introduction • Computer System Categories • Parallel Architectures • Principles for Parallelism Analysis • Exercises • The PRAM Model • Exercises • Simple Parallel Operations • Broadcasting Data in a CREW PRAM Model • Broadcasting Data in an EREW PRAM Model • Finding the Maximum Value in a List • Exercises • Parallel Searching • Exercises • Parallel Sorting • Linear Network Sort • Odd-Even Swap Sort • Other Parallel Sorts • Exercises • Parallel Numerical Algorithms • Matrix Multiplication on a Parallel Mesh • Matrix Multiplication in a CRCW PRAM Model • Solving Systems of Linear Equations with an SIMD Algorithm • Exercises • Parallel Graph Algorithms • All Pairs Shortest-Path Parallel Algorithm • Minimum Spanning Tree Parallel Algorithm • Exercises

Chapter 10: Limits of Computation • Turing Machines • Turing Machines as Language Acceptors • Turing Machines as Function Calculators • Designing Turing Machines • Exercises • The Church?Turing Thesis • Turing Machine Variations • Two-Way Infinite Tape Turing Machines • Multiple Tape Turing Machines • Two-Dimensional Tape Turing Machines • Nondeterministic Turing Machines • A Universal Turing Machine • Exercises • The Limits of Turing Machines • Languages Not Recursively Enumerable • The Halting Problem • Exercise • What is NP? • Problem Reductions • NP-Complete Problems • Typical NP Problems • Graph Coloring • Bin Packing • Backpack Problem • Subset Sum Problem • CNF-Satisfiability Problem • Job Scheduling Problem • Exercises • What Makes Something NP? • Is P = NP? • Exercises • Testing Possible Solutions • Job Scheduling • Graph Coloring • Exercises

Chapter 11: Other Algorithmic Techniques • Greedy Approximation Algorithms • Traveling Salesperson Approximations • Bin Packing Approximations • Backpack Approximation • Subset Sum Approximation • Graph Coloring Approximation • Exercises • Backtracking • Exercises • Branch and Bound • Exercises • Probabilistic Algorithms • Numerical Probabilistic Algorithms • Monte Carlo Algorithms • Las Vegas Algorithms • Sherwood Algorithms • Probabilistic Algorithm Comparison • Exercises • Dynamic Programming • Calculating Fibonacci Numbers and Binomial Coefficients • Dynamic Matrix Multiplication • Floyd's All-Pairs Shortest Path Algorithm • A Dynamic Algorithm for the Backpack Problem • Exercises • Programming Exercises

Appendix A Pseudorandom Number Table
Appendix B Pseudorandom Number Generation: B.1 Generating Numbers in a Different Range • B.2 Example Application • B.2.1 Method 1 • B.2.2 Method 2 • B.2.3 Method 3
Appendix C Results of Chapter Study Suggestions
Appendix D References
Index

Preface

Chapter 1: Analysis Basics • What is Analysis? • Input Classes • Space Complexity • Exercises • What to Count and Consider • Cases to Consider • Exercises • Mathematical Background • Logarithms • Binary Trees • Probabilities • Summations • Exercises • Rates of Growth • Classification of Growth • Exercises • Tournament Method • Lower Bounds • Exercises • Analyzing Programs

Chapter 2: Recursive Algorithms • Analyzing Recursive Algorithms • Exercises • Recurrence Relations • Approximating the Order of a Recurrence Relation • Exercises • Closest Pair • Exercises • Convex Hull • Exercises • Generating Permutations • Exercises • Recursion and Stacks • Programming Exercises

Chapter 3: Searching and Selection Algorithms • Sequential Search • Worst-Case Analysis • Average-Case Analysis • Exercises • Binary Search • Worst-Case Analysis • Average-Case Analysis • Exercises • Selection • Exercises • Programming Exercise

Chapter 4: Sorting Algorithms • Insertion Sort • Worst-Case Analysis • Average-Case Analysis • Exercises • Bubble Sort • Best-Case Analysis • Worst-Case Analysis • Average-Case Analysis • Exercises • Shellsort • Algorithm Analysis • The Effect of the Increment • Exercises • Radix Sort • Analysis • Exercises • Heapsort • Worst-Case Analysis • Average-Case Analysis • Exercises • Merge Sort • MergeLists Analysis • MergeSort Analysis • Exercises • Quicksort • Worst-Case Analysis • Average-Case Analysis • Exercises • External Polyphase Merge Sort • Number of Comparisons in Run Construction • Number of Comparisons in Run Merge • Number of Block Reads • Exercises • Additional Exercises • Programming Exercises

Chapter 5: Numeric Algorithms • Calculating Polynomials • Horner's Method • Preprocessed Coefficients • Exercises • Matrix Multiplication • Winograd's Matrix Multiplication • Strassen's Matrix Multiplication • Exercises • Linear Equations • Gauss?Jordan Method • Exercises

Chapter 6: Formal Language Algorithms • Formal Language Basics • Lexical Ordering • Language Classifications • Exercises • Finite Auomata • Regular Languages • Regular Expression • Regular Grammars • Dererminate and Nondeterministic Finite Automata • Converting a Deterministic Finite Automaton into a Program • Exercises • Designing Finite Automata • Finite Automata Restrictions • Designing a Finite Automaton • Designing a Regular Grammar • Exercises • Finite Automata Equivalence and Limitations • Limits on Finite Automata • Exercises • Pushdown Automata • Creating a Deterministic Pushdown Automaton • Deterministic Context-Free Languages • Nondeterministic Pushdown Automata • Exercises • Context-Free Grammars • Context-Free Grammar Abilities • Designing Context-Free Grammars • Grammar Transformation • Greibach Normal Form • Converting a Context-Free Grammar into a Pushdown Automaton • Exercises • Limitations of Pushdown Automata • Exercises • Programming Language Compilation • Exercises

Chapter 7: Matching Algorithms • String Machine ?Finite Automata • Knuth?Morris?Pratt Algorithm • Boyer?Moore Algorithm • Exercises • Approximate String Matching • Analysis • Exercises • Programming Exercises

Chapter 8: Graph Algorithms • Graph Background and Terminology • Terminology • Exercises • Data Structure Methods for Graphs • The Adjacency Matrix • The Adjacency List • Exercises • Depth-First and Breadth-First Traversal Algorithms • Depth-First Traversal • Breadth-First Traversal • Traversal Analysis • Exercises • Minimum Spanning Tree Algorithm • The Dijkstra?Prim Algorithm • The Kruskal Algorithm • Exercises • Shortest-Path Algorithm • Dijkstra's Algorithm • Exercises • Biconnected Component Algorithm • Exercises • Partitioning Sets • Programming Exercises

Chapter 9: Parallel Algorithms • Parallelism Introduction • Computer System Categories • Parallel Architectures • Principles for Parallelism Analysis • Exercises • The PRAM Model • Exercises • Simple Parallel Operations • Broadcasting Data in a CREW PRAM Model • Broadcasting Data in an EREW PRAM Model • Finding the Maximum Value in a List • Exercises • Parallel Searching • Exercises • Parallel Sorting • Linear Network Sort • Odd-Even Swap Sort • Other Parallel Sorts • Exercises • Parallel Numerical Algorithms • Matrix Multiplication on a Parallel Mesh • Matrix Multiplication in a CRCW PRAM Model • Solving Systems of Linear Equations with an SIMD Algorithm • Exercises • Parallel Graph Algorithms • All Pairs Shortest-Path Parallel Algorithm • Minimum Spanning Tree Parallel Algorithm • Exercises

Chapter 10: Limits of Computation • Turing Machines • Turing Machines as Language Acceptors • Turing Machines as Function Calculators • Designing Turing Machines • Exercises • The Church?Turing Thesis • Turing Machine Variations • Two-Way Infinite Tape Turing Machines • Multiple Tape Turing Machines • Two-Dimensional Tape Turing Machines • Nondeterministic Turing Machines • A Universal Turing Machine • Exercises • The Limits of Turing Machines • Languages Not Recursively Enumerable • The Halting Problem • Exercise • What is NP? • Problem Reductions • NP-Complete Problems • Typical NP Problems • Graph Coloring • Bin Packing • Backpack Problem • Subset Sum Problem • CNF-Satisfiability Problem • Job Scheduling Problem • Exercises • What Makes Something NP? • Is P = NP? • Exercises • Testing Possible Solutions • Job Scheduling • Graph Coloring • Exercises

Chapter 11: Other Algorithmic Techniques • Greedy Approximation Algorithms • Traveling Salesperson Approximations • Bin Packing Approximations • Backpack Approximation • Subset Sum Approximation • Graph Coloring Approximation • Exercises • Backtracking • Exercises • Branch and Bound • Exercises • Probabilistic Algorithms • Numerical Probabilistic Algorithms • Monte Carlo Algorithms • Las Vegas Algorithms • Sherwood Algorithms • Probabilistic Algorithm Comparison • Exercises • Dynamic Programming • Calculating Fibonacci Numbers and Binomial Coefficients • Dynamic Matrix Multiplication • Floyd's All-Pairs Shortest Path Algorithm • A Dynamic Algorithm for the Backpack Problem • Exercises • Programming Exercises

Appendix A Pseudorandom Number Table
Appendix B Pseudorandom Number Generation: B.1 Generating Numbers in a Different Range • B.2 Example Application • B.2.1 Method 1 • B.2.2 Method 2 • B.2.3 Method 3
Appendix C Results of Chapter Study Suggestions
Appendix D References
Index


About the Author:

Jeffrey McConnell, Canisius College
Jeffrey J. McConnell has a Ph.D. in Computer Science from Worcester Polytechnic Institute (1988), a M.S. in Computer Science from SUNY at Buffalo (1986), and a B.A. in Mathematics from Canisius College.  Jeffrey J. McConnell is a full Professor at Canisius College where he has been a member of the faculty since 1983.  He has served as department chair there since 1990.  In 1993, he received the I. Joan Lorch Women's Studies Award for his contributions to women at Canisius College, and received a Robert H. Goddard Fellowship from Worcester Polytechnic Institute (1987-88).

Dr. McConnell  is a proponent of active and cooperative learning.  He has incorporated this into his teaching pedagogy at a high level since 1993.  He has four publications on active learning and has given 15 workshops on the topic.  He was the featured speaker at George Washington University's 1997 Fall Teaching Colloquium and was the luncheon speaker for Rochester Institute of Technology's Insight 98 conference.  He has created a web site with active and cooperative learning information.  He also has 14 publications in the area of Computer Graphics.

About the Author:

Jeffrey McConnell, Canisius College
Jeffrey J. McConnell has a Ph.D. in Computer Science from Worcester Polytechnic Institute (1988), a M.S. in Computer Science from SUNY at Buffalo (1986), and a B.A. in Mathematics from Canisius College.  Jeffrey J. McConnell is a full Professor at Canisius College where he has been a member of the faculty since 1983.  He has served as department chair there since 1990.  In 1993, he received the I. Joan Lorch Women's Studies Award for his contributions to women at Canisius College, and received a Robert H. Goddard Fellowship from Worcester Polytechnic Institute (1987-88).
 

Dr. McConnell  is a proponent of active and cooperative learning.  He has incorporated this into his teaching pedagogy at a high level since 1993.  He has four publications on active learning and has given 15 workshops on the topic.  He was the featured speaker at George Washington University's 1997 Fall Teaching Colloquium and was the luncheon speaker for Rochester Institute of Technology's Insight 98 conference.  He has created a web site with active and cooperative learning information.  He also has 14 publications in the area of Computer Graphics.