Methods in Algorithmic Analysis
eBook - PDF

Methods in Algorithmic Analysis

Vladimir A. Dobrushkin

  1. 824 pages
  2. English
  3. PDF
  4. Available on iOS & Android
eBook - PDF

Methods in Algorithmic Analysis

Vladimir A. Dobrushkin

Book details
Table of contents
Citations

About This Book

Explores the Impact of the Analysis of Algorithms on Many Areas within and beyond Computer Science
A flexible, interactive teaching format enhanced by a large selection of examples and exercises

Developed from the author's own graduate-level course, Methods in Algorithmic Analysis presents numerous theories, techniques, and methods used for analyzing algorithms. It exposes students to mathematical techniques and methods that are practical and relevant to theoretical aspects of computer science.

After introducing basic mathematical and combinatorial methods, the text focuses on various aspects of probability, including finite sets, random variables, distributions, Bayes' theorem, and Chebyshev inequality. It explores the role of recurrences in computer science, numerical analysis, engineering, and discrete mathematics applications. The author then describes the powerful tool of generating functions, which is demonstrated in enumeration problems, such as probabilistic algorithms, compositions and partitions of integers, and shuffling. He also discusses the symbolic method, the principle of inclusion and exclusion, and its applications. The book goes on to show how strings can be manipulated and counted, how the finite state machine and Markov chains can help solve probabilistic and combinatorial problems, how to derive asymptotic results, and how convergence and singularities play leading roles in deducing asymptotic information from generating functions. The final chapter presents the definitions and properties of the mathematical infrastructure needed to accommodate generating functions.

Accompanied by more than 1, 000 examples and exercises, this comprehensive, classroom-tested text develops students' understanding of the mathematical methodology behind the analysis of algorithms. It emphasizes the important relation between continuous (classical) mathematics and discrete mathematics, which is the basis of computer science.

Frequently asked questions

Simply head over to the account section in settings and click on “Cancel Subscription” - it’s as simple as that. After you cancel, your membership will stay active for the remainder of the time you’ve paid for. Learn more here.
At the moment all of our mobile-responsive ePub books are available to download via the app. Most of our PDFs are also available to download and we're working on making the final remaining ones downloadable now. Learn more here.
Both plans give you full access to the library and all of Perlego’s features. The only differences are the price and subscription period: With the annual plan you’ll save around 30% compared to 12 months on the monthly plan.
We are an online textbook subscription service, where you can get access to an entire online library for less than the price of a single book per month. With over 1 million books across 1000+ topics, we’ve got you covered! Learn more here.
Look out for the read-aloud symbol on your next book to see if you can listen to it. The read-aloud tool reads text aloud for you, highlighting the text as it is being read. You can pause it, speed it up and slow it down. Learn more here.
Yes, you can access Methods in Algorithmic Analysis by Vladimir A. Dobrushkin in PDF and/or ePUB format, as well as other popular books in Computer Science & Programming Algorithms. We have over one million books available in our catalogue for you to explore.

Information

Publisher
Chapman and Hall/CRC
Year
2016
ISBN
9781420068306
Edition
1
Topic
Computer Science
Subtopic
Programming Algorithms
Index
Computer Science

Table of contents

  1. Front Cover
  2. Contents
  3. Preface
  4. Acknowledgments
  5. List of Symbols
  6. Abbreviations
  7. Dedication
  8. Chapter 1: Preliminaries
  9. Chapter 2: Combinatorics
  10. Chapter 3: Probability
  11. Chapter 4: More about Probability
  12. Chapter 5: Recurrences or Difference Equations
  13. Chapter 6: Introduction to Generating Functions
  14. Chapter 7: Enumeration with Generating Functions
  15. Chapter 8: Further Enumeration Methods
  16. Chapter 9: Combinatorics of Strings
  17. Chapter 10: Introduction to Asymptotics
  18. Chapter 11: Asymptotics and Generating Functions
  19. Chapter 12: Review of Analytic Techniques
  20. Appendices
  21. Answers/Hints to Selected Problems
  22. Bibliography
  23. Back Cover