Practical analysis of algorithms

DOI10.1007/978-3-319-09888-3MaRDI QIDQ461086zbMATH OpenOpenAlexFDO

Authors Dana Vrajitoru, William J. Knight

Publication date 9 October 2014

Published in Undergraduate Topics in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-09888-3

zbMATH Keywords

algorithm analysisfinite graph algorithmsrecurrence relations

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Data structures (68P05) Searching and sorting (68P10) General topics in the theory of algorithms (68W01) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Review text

The book is dedicated to an old, important and complex topic in computer science. The novelty of the book is that its approach is based on numerous examples combined with the classical theory based on theorems and proofs. The books starts with mathematically simple preliminaries like logarithms, sums, factorials or integer division. Then the fundamental notations in the analysis of algorithms are introduced, and later on recurrence relations. Deterministic analysis of algorithms is done in relationship with loops, binary trees, priority queues, binary heaps, merge sorts, quicksort, pattern matching. Another chapter is dedicated to algorithms that use randomized procedures, like simulating random events or selecting a random sample from a population; for those algorithms the expected value theorems are presented and discussed. Particularly interesting for programmers are the applications of expected value theorems and conditional expected value to the analysis of algorithms. Finally, finite graph algorithms are the subject of algorithm analysis. The multiple exercises in each section invite the readers to a deeper exploration of the subjects. The formalized style of the book is expected to attract especially young students introduced already to mathematical formalisms. The material can be used as a textbook for undergraduate courses in computer science.

Recommendations

• An Introduction to the Analysis of Algorithms
• scientific article; zbMATH DE number 4058818
• An Introduction to the Analysis of Algorithms
• scientific article; zbMATH DE number 976346
• Applied Genetic Programming and Machine Learning

Cited in

(9)

• Algorithm analysis through proof complexity
• ON THE MAXIMUM NUMBER OF PERIOD ANNULI FOR SECOND ORDER CONSERVATIVE EQUATIONS
• scientific article; zbMATH DE number 108389 (Why is no real title available?)
• scientific article; zbMATH DE number 976346 (Why is no real title available?)
• Algorithmics of nonuniformity: tools and paradigms
• Analytic analysis of algorithms
• Applied Genetic Programming and Machine Learning
• An introduction to the analysis of algorithms.
• An Introduction to the Analysis of Algorithms

This page was built for publication: Practical analysis of algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q461086)