Viva Group has been honoured with the Best Publisher Award 2022 by the Delhi State Booksellers & Publishers' Association.

Analysis of Algorithms, 2/e

Analysis of Algorithms, 2/e

Analysis of Algorithms, 2/e

An Active Learning Approach

  • By: Jeffery J. McConnell

₹805.50 ₹895.00 Save: ₹89.50 (10%)

Go to cart
  • Out of Stock

ISBN: 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:

  • All algorithms are presented in pseudocode that is understandable to a broad range of readers.
  • Includes new material on finite automata, pushdown automata, context-free grammars, and Turing Machines.
  • A new chapter on Recursive Algorithms adds discussion on approximating the order of a recurrence relation.
  • Numerous examples and real-world programming projects encourage students to become active participants in the classroom.
  • An online Instructor's Manual provides solutions and course material that discuss how to teach using an active and cooperative learning approach.


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.

10%

The Metaverse (on procurement ..

By: Matthew Ball

ISBN : 9781324092032

₹ 2,300.40 ₹ 2,556.00

10%

Writing Fast Programs with CD

By: John Riley

ISBN : 9789386385901

₹ 895.50 ₹ 995.00

10%

Software Extension to the PMBO..

By: IEEE Computer Society

ISBN : 9789387486843

₹ 805.50 ₹ 895.00

10%

Discrete Structures, Logic, an..

By: James L. Hein

ISBN : 9789384323264

₹ 895.50 ₹ 995.00

10%

An Introduction to Formal Lang..

By: Peter Linz

ISBN : 9789384323219

₹ 625.50 ₹ 695.00

10%

Foundations of Algorithms, 5/e

By: Richard E Neapolitan

ISBN : 9789384323110

₹ 805.50 ₹ 895.00