Practical Analysis of Algorithms

✍ Scribed by Dana Vrajitoru, William Knight (auth.)

• Publisher: Springer International Publishing
• Year: 2014
• Tongue: English
• Leaves: 475
• Series: Undergraduate Topics in Computer Science
• Edition: 1
• Category: Library

✦ Synopsis

This book introduces the essential concepts of algorithm analysis required by core undergraduate and graduate computer science courses, in addition to providing a review of the fundamental mathematical notions necessary to understand these concepts. Features: includes numerous fully-worked examples and step-by-step proofs, assuming no strong mathematical background; describes the foundation of the analysis of algorithms theory in terms of the big-Oh, Omega, and Theta notations; examines recurrence relations; discusses the concepts of basic operation, traditional loop counting, and best case and worst case complexities; reviews various algorithms of a probabilistic nature, and uses elements of probability theory to compute the average complexity of algorithms such as Quicksort; introduces a variety of classical finite graph algorithms, together with an analysis of their complexity; provides an appendix on probability theory, reviewing the major definitions and theorems used in the book.

✦ Table of Contents

Front Matter....Pages i-xii
Introduction....Pages 1-7
Mathematical Preliminaries....Pages 9-62
Fundamental Notations in Analysis of Algorithms....Pages 63-94
Recurrence Relations....Pages 95-167
Deterministic Analysis of Algorithms....Pages 169-293
Algorithms and Probabilities....Pages 295-360
Finite Graph Algorithms....Pages 361-452
Appendix: Probability Theory....Pages 453-462
Back Matter....Pages 463-466

✦ Subjects

Algorithm Analysis and Problem Complexity; Logics and Meanings of Programs; Programming Techniques; Algorithms