₹805.50 ₹895.00 Save: ₹89.50 (10%)
Go to cartISBN: 9789384323189
Bind: Paperback
Year: 2017
Pages: 470
Size: 172 x 216 mm
Publisher: Jones & Bartlett Learning
Published in India by: Jones & Bartlett India
Exclusive Distributors: Viva Books
Sales Territory: India, Nepal, Pakistan, Bangladesh, Sri Lanka
Description:
Updated to follow the recommendations put forth by the ACM/SIGCSE 2001 task force, Analysis of Algorithms: An Active Learning Approach, Second Edition raises readers- awareness of the effects that algorithms have on the efficiency of a program, and helps students develop the skills necessary to analyze the algorithms used in effective programming. Based on the highly successful active learning approach, Jeffery McConnell developed the text with the premise that students learn more effectively and retain information longer when they are active participants in the learning process. To accomplish this, chapters are clear, complete, student- friendly, and filled with exciting examples and exercises that examine the efficiency of various algorithms to solve meaningful, real-world problems.
Key Features of Analysis of Algorithms: An Active Learning Approach, Second Edition:
Target Audience:
This book is helpful for the students and academicians of Computer Science.
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.