Practical Analysis of Algorithms (Undergraduate Topics in Computer Science) （2014）

Vrajitoru, Dana/ Knight, William

Springer International Publishing AG（2014/09発売）

• 製本 Paperback:紙装版/ペーパーバック版／ページ数 466 p.
• 言語 ENG
• 商品コード 9783319098876
• DDC分類 005.1

Full Description

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.

Contents

Introduction.- Mathematical Preliminaries.- Fundamental Notations in Analysis of Algorithms.- Recurrence Relations.- Deterministic Analysis of Algorithms.- Algorithms and Probabilities.- Finite Graph Algorithms.- Appendix: Probability Theory.